质因数分解-函数

标签：正整数 因数分解 int 质数 样例 输入 函数

题目描述

原题来自：NOIP 2012 普及组 
已知正整数 n  是两个不同的质数的乘积，试求出较大的那个质数。

输入格式

输入只有一行，包含一个正整数 n  。

输出格式

输出只有一行，包含一个正整数 p ，即较大的那个质数。

输入样例 

21

输出样例 

7

数据范围与提示

数据范围与提示：

对于 30% 的数据，n≤1000；

对于全部数据，6≤n≤2×109 。

#include<iostream>
using namespace std;

bool isPrime(int x){
    for(int i=2; i*i<=x; i++){
        if(x%i==0) 
            return 0;
    }
    return 1;
}

int main(){
    int n;
    cin>>n;
    for(int i=2; i*i<=n; i++){
        // n=最小质数*最大质数。
        if(isPrime(i) && n%i==0){
            cout<<n/i;
            break;
        } 
    }
    return 0;
}

 

标签：正整数,因数分解,int,质数,样例,输入,函数
From： https://www.cnblogs.com/dks0313/p/16610346.html