【C++ 真题】P1075 [NOIP 2012 普及组] 质因数分解

P1075 [NOIP 2012 普及组] 质因数分解

题目描述

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

输入格式

输入一个正整数 $n$。

输出格式

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

输入输出样例 #1

输入 #1

21

输出 #1

7

说明/提示

$1\le n\le 2\times 10^9$

NOIP 2012 普及组 第一题

题解

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

bool is_prime(int x){
	if(x <= 1) return false;
	for(int i=2;i<=x/i;++i){
		if(x % i == 0) return false;
	}
	return true;
}

int main(){
	cin>>n;
	for(int i=1;i<=n/i;i++){
		if(n%i == 0 && is_prime(i) && is_prime(n/i)){
			cout<<n/i<<endl;
			return 0;
		}
	}
	return 0;	
}