[C++知识库]P1075 [NOIP2012 普及组] 质因数分解

P1075 [NOIP2012 普及组] 质因数分解

题目描述

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

输入格式

一个正整数n。

输出格式

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

输入输出样例

输入 #1复制

21

输出 #1复制

7

说明/提示

$n\le 2\times 10^9$

NOIP 2012 普及组 第一题

题解

python

def isPrime(a:int):
    if a==2:return True
    for i in range(2,int(a**0.5)+1):
        if a%i==0:return False
    return True

n=eval(input())
for i in range(2,int(n**0.5)+1):
    if isPrime(i):
        if n%i==0 and isPrime(n//i):
            print(max(i,n//i))
            break

c++

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;
int n;

bool isPrime(int a){
    if (a==2) return true;
    for (int i = 2; i < ceil(pow(a,0.5)); ++i) {
        if(a%i==0)return false;
    }
    return true;
}
int main() {
    cin >> n;
    for (int i = 2; i < ceil(pow(n,0.5)); ++i) {
        if(isPrime(i)){
            if(n%i==0 && isPrime(n/i)){
                cout<<max(i,n/i);
                break;
            }
        }
    }

    return 0;
}