• P1075 [NOIP2012 普及組] 質因數分解

[NOIP2012 普及組] 質因數分解

題目描述

已知正整數 \(n\) 是兩個不同的質數的乘積，試求出兩者中較大的那個質數。

輸入格式

輸入一個正整數 \(n\)。

輸出格式

輸出一個正整數 \(p\)，即較大的那個質數。

樣例 #1

樣例輸入 #1

21

樣例輸出 #1

7

提示

\(1 \le n\le 2\times 10^9\)

NOIP 2012 普及組 第一題

• 參考程序

#include<bits/stdc++.h>
#include<string>
using namespace std;

bool isp(int n){
    for(int i=2; i<=n/i; i++) {
        if(n%i==0) return 0;
    }
    return n > 1;
}
int main(){
    int n; cin>>n;
    for(int i=2; i<n/i; i++){
        if(n%i==0 && isp(i) && isp(n/i)){
            cout<<n/i; break;
        }
    }
    return 0;
}