[NOIP2012 普及组] 质因数分解

题目描述

已知正整数 nn 是两个不同的质数的乘积，试求出两者中较大的那个质数。

输入格式

输入一个正整数 nn。

输出格式

输出一个正整数 pp，即较大的那个质数。

样例 #1

样例输入 #1

1
21

样例输出 #1

1
7

提示

1≤n≤2×1091 \le n\le 2\times 10^9

NOIP 2012 普及组 第一题

题解

1
2
3
4
5
6
7
8
9
10
11
import math

n = int(input())
i = 2
while i <= math.sqrt(n):
    if n % i == 0:
        break
    i = i + 1

print(int(n / i))

题解解释

这道题要求解一个正整数 nn，该整数是两个不同质数的乘积。你需要找出这两个质数中较大的那个，并输出。

解题思路：

  1. 首先导入math库。
  2. 通过循环，从 i=2i=2 开始逐步增加 ii 的值，直到 ii 大于等于 nn 的平方根。
  3. 在循环中，检查是否 nn 能被 ii 整除，如果是，则说明找到了一个质因数，即 ii。
  4. 输出 nn 除以 ii 的结果，即较大的那个质数。

在给定的代码中，如果输入是21，那么循环会找到2是21的一个因数，然后输出21除以2的结果，即7。因此，输出为7，是较大的那个质数。

知识点

找质因数的时候，可以用平方根来提高查找速率