质因数分解

题意

已知正整数 $n$ 是两个不同质数的乘积，输出其中较大的质数。

思路

从 $2$ 开始寻找能整除 $n$ 的最小因子。因为 $n$ 恰好是两个不同质数的乘积，这个最小因子就是较小质数，另一个因子 number // divisor 就是答案。

只需检查到 divisor * divisor <= number；若两个因子都大于平方根，它们的乘积会超过 $n$ 。

代码

Python代码

python

1
2
3
4
5
6
7
8number = int(input())
divisor = 2

while divisor * divisor <= number:
    if number % divisor == 0:
        print(number // divisor)
        break
    divisor += 1

C++代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28#include <cstdio>
#include <cmath>

bool is_prime(int n){
    int i;
    for(i=2;i<=(int)sqrt(n);i++ ){
        if( n % i ==0)
            return 0;
    }
    return 1;
}


int main(){
    int n;
    scanf("%d",&n);
    int i;
    for (i=1;i<=n;i++){
        if( n % i == 0 && is_prime(i)){
            int a = n / i;
            if( is_prime(a)){
                printf("%d\n",a);
                return 0;
            }
        }
    }
    return 0;
}

复杂度

最坏情况下枚举到 $\sqrt n$ ，时间复杂度为 $O(\sqrt n)$ ，额外空间复杂度为 $O(1)$ 。

总结

已知乘积结构时，找到一边的因子就能用整除立即得到另一边。

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结