Problem Address：http://acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1645
这道题开始看起来好像好点难，但是实际上并不是如此。
有10000组数据，又要在1000MS内完成，每个数又是在[1,2000000]内。
再看一下题目，如果不是素数则输出0。那么是素数呢？
随便求几个素数之后就可以发现该素数减一就是答案。
所以这道题其实就是判断素数。
我用了朴素筛选。速度也不是很慢。
以下贴代码：
//Time：94MS Memory：2116K
#include <iostream>using namespace std;const int maxn=2000005;bool *notprime = (bool*)malloc(sizeof(bool)*maxn);int main(){ int n,i,j; notprime[0]=true; notprime[1]=true; for (i=2; i<maxn; i++) notprime[i]=false;
for (i=2; i<maxn; i++)//该循环是朴素筛选 { if (!notprime[i]) { if (i*i>maxn) break;//对某个素数的平方以上的倍数进行筛选 for (j=i*i; j<maxn; j+=i) notprime[j]=true; } } while(scanf("%d", &n)!=EOF) { if (notprime[n]) printf("0/n"); else printf("%d/n", n-1); }
free(notprime); return 0;}
刚写完这个解题报告马上又去试了一下线性筛选：
代码如下：
//线性筛选利用的是每个合数都有一个最小质因子
//Time：78MS Memory：9948K
#include <iostream>using namespace std;const int maxn=2000005;bool *notprime = (bool*)malloc(sizeof(bool)*maxn);int *primelist = (int*)malloc(sizeof(int)*maxn);int primenum;int main(){ int n,i,j; notprime[0]=true; notprime[1]=true; for (i=2; i<maxn; i++) notprime[i]=false; for (i=4; i<maxn; i+=2) notprime[i]=true;//把偶数筛掉 primenum = 0; for (i=3; i<maxn; i+=2) { if (!notprime[i])//如果是质数就加入质数列表 { primelist[primenum] = i; primenum++; } for (j=0; j<primenum && i*primelist[j]<maxn; j++)//对为筛选的数进行筛选 { notprime[i*primelist[j]] = true;//以质因子的倍数进行筛选 if (i%primelist[j]==0) break;//如果primelist[j]是i的最小质因子，则也是i*primelist[j]的最小质因子 } } while(scanf("%d", &n)!=EOF) { if (notprime[n]) printf("0/n"); else printf("%d/n", n-1); }
free(notprime);
free(primelist); return 0;}
结果时间上还是差不多，可能是因为数据量比较小的缘故。但是空间上却差别有点大。
p.s.今天又做了一道prim算法的题，debug之后一次AC。哈哈哈~继续加油啦~~（这个p.s.是刚才的……）
