【问题描述】 已知正整数 n 是两个不同的质数的乘积,试求出较大的那个质数。 【输入】 输入文件名为 prime.in。 输入只有一行,包含一个正整数 n。 【输出】 输出文件名为 prime.out。 输出只有一行,包含一个正整数 p,即较大的那个质数。 【样例】 输入： 21 输出： 7
注意： 1）认真读题，我一开始把这道题写成了《分解质因数》，没考虑到问题描述。 2）先判断质数，再判断因数;而我是先判断因数，再判断质数，导致超时。 知识点： 1）一个数的质因数个数不超过n（2^n） 2）亿后面的数位:兆、京、垓、秭、穰、沟、涧、正、载、极 3）判断一个数是否是质数，只要i×i就可以了，减少很多循环次数
测试数据下载 NOIP2012年普及组复赛试题第1题《质因数分解》测试数据10组
#include<iostream> #include<cstdio> using namespace std; int main(void) { freopen("prime.in","r",stdin); freopen("prime.out","w",stdout); int n,i; cin>>n; for(i=2;i*i<=n;i++) { if(n%i==0) { cout<<n/i<<endl; break; } } fclose(stdin); fclose(stdout); return 0; }