NOIP2012普及组复赛试题及解答

《NOIP2012普及组复赛试题及解答》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、全国信息学奥林匹克联赛（NOIP2012）复赛试题及解答普及组CCF全国信息学奥林匹克联赛（NOIP2012）复赛普及组（请选手务必仔细阅读本页内容）一．题目概况中文题目名称质因数分解寻宝摆花文化之旅英文题目与子目录primetreasureflowerculture可执行文件名primetreasureflowerculture输入文件名prime.intreasure.inflower.inculture.in输出文件名prime.outtreasure.outflower.outculture.out每个测试点时限1秒1秒1秒1秒测试点数目101010

2、10每个测试点分值10101010附加样例文件有有有有结果比较方式全文比较（过滤行末空格及文末回车）题目类型传统传统传统传统二．提交源程序文件名对于C++语言prime.cpptreasure.cppflower.cppculture.cpp对于C语言prime.ctreasure.cflower.cculture.c对于pascal语prime.pastreasure.pasflower.pasculture.pas言三．编译命令（不包含任何优化开关）对于C++语言g++-oprimeg++-otreasureg++-oflowerg++-oculture

3、prime.cpp-lmtreasure.cpp-lmflower.cpp-lmculture.cpp-lm对于C语言gcc-oprimegcc-otreasuregcc-oflowergcc-ocultureprime.c-lmtreasure.c-lmflower.c-lmculture.c-lm对于pascal语fpcprime.pasfpcfpcflower.pasfpcculture.past四．运行内存限制内存上限128M128M128M128M注意事项：1、文件名（程序名和输入输出文件名）必须使用英文小写。2、C/C++中函数main()的返回

4、值类型必须是int，程序正常结束时的返回值必须是0。3、全国统一评测时采用的机器配置为：CPUIntelCore2QuadQ82002.33GHz，内存2G，上述时限以此配置为准。4、特别提醒：评测在NOILinux下进行。第1页共10页全国信息学奥林匹克联赛（NOIP2012）复赛试题及解答普及组1.质因数分解(prime.cpp/c/pas)【问题描述】已知正整数n是两个不同的质数的乘积，试求出较大的那个质数。【输入】输入文件名为prime.in。输入只有一行，包含一个正整数n。【输出】输出文件名为prime.out。输出只有一行，包含一个正整数p，即较

5、大的那个质数。【输入输出样例】prime.inprime.out217【数据范围】9对于60%的数据，6≤n≤1000。对于100%的数据，6≤n≤2*10。[解题思路]1.根据数据范围，可以判断数据范围为长整型（long=4bytes）补充数据类型：整型char1byteInt4bytesShort2bytesLong4bytesLonglong8bytes程序：#include#include#includeinta[44722]={0};//用于筛选法求素数,有题目数据范围可知,涉及到的最大素数一定

6、小于44722intb[10000]={0};//用于存储素数,b[i]用于存储第i+1个素数intcount=0;voidcalculatePrime(void)//筛选法求素数，主要考虑到时间效率，所以用此法求素数{inti,j;memset(a,-1,sizeof(a));memset(b,0,sizeof(b));a[0]=a[1]=0;for(i=2;i<50000;i++){if(a[i]==-1){for(j=i+i;j<50000;j+=i){a[j]=0;}}}for(i=2;i<50000;i++)第2页共10页全国信息学奥林匹克联赛（N

7、OIP2012）复赛试题及解答普及组{if(a[i]==-1){b[count++]=i;}}}intmain(void){inti,n,squre,temp;FILE*inputfp;FILE*outputfp;calculatePrime();inputfp=fopen("prime.in.txt","r");outputfp=fopen("prime.out.txt","w");while(fscanf(inputfp,"%d",&n)!=EOF){printf("%d",n);squre=(int)sqrt(n);for(i=0;i<=squre&&

8、i