[NOIP2012 普及组] 质因数分解

题目描述

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

输入格式

输入一个正整数 $n$。

输出格式

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

样例 #1

样例输入 #1

1
21

样例输出 #1

1
7

提示

$1 \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))

题解解释

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

解题思路：

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

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

知识点

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