题目来源-洛谷

题目描述
已知正整数n是两个不同的质数的乘积,试求出两者中较大的那个质数。

输入格式
一个正整数n。

输出格式
一个正整数p,即较大的那个质数。

输入样例

21

输出样例

7

说明/提示
n<=2*10^9

本题只需从小开始寻找n的质因数,当找到一个时判断其对应的另外一个因数是否为质数。若是,则输出、退出,若否则继续寻找。
由简单的数学归纳可得n的一个小的质因数不会大于sqrt(n)

代码:

#include<bits/stdc++.h>
using namespace std;
bool prime(int x){
    int range=sqrt(x)+1;
    for(int i=2;i<=range;i++)if(x%i==0)return false;
    return true;
}
int main(){
    int n,leftn,t;
    cin>>n;
    leftn=sqrt(n)+1;
    for(int i=2;i<=leftn;i++){
        if(n%i==0){
            t=n/i;
            if(prime(t)){
                printf("%d",t);
                return 0;
            }
            else continue;
        }
        else continue;
    }
    return 0;
}
Last modification:October 10th, 2021 at 10:21 pm
If you think my article is useful to you, please feel free to appreciate