数素数（http://acm.tongji.edu.cn/showproblem.php?problem_id=1010）Problem素数是的只能被1和它本身整除的自然数。判断一个数是素数的方法是使用2到该数的平方根的素数除它，若有能整除的则该数不是素数。 其实是个简单问题，但对于给出的数据范围（0<M<N<1000000），总是迫使我寻找更快更省的方法。一开始我就想找到一种数学方法，如果找到了当然是最快最省的，但是，还没找到，于是只好用笨的方法。1、用素数的定义 素数是的只能被1和它本身整除的自然数。那就从2到sqrt(n)进行试除，如果有一个数能整除n，那n就不是素数，否则n就是素数。 如果不仔细想，会认为这样做已经是非常快了，其实做了很多多余的工作，以下简单分析：首先从奇偶性上看，所有的素数中只有2是偶数，也就是说几乎所有素数都是奇数，而在试除的过程中，我们还用4,6,8之类的偶数去试除，真是愚蠢到家了。同样的道理，如果3不能整除的，那所有的3的倍数也不能整除，那也不必用6,9,12去试除了。 稍微进行改进的方法是，建立素数表，于是判断一个数n是否是素数就可以用2到sqrt(n)间的素数去除n，如果有一个素数能整除n，那n就不是素数，否则n就是素数。 我说‘稍微’改进，实际上对于基于‘试除’的求素数方法，已经是达到了极致，同时对于n比较大的数，进行试除次数也会大大降低。以下数据可以说明问题：n= sqrt(n)= 直接试除次数 基于素数表试除次数 10000 100 98 25 50000 223 221 49 100000 316 314 67 500000 707 705 1281000000 1000 998 168代码：#include<stdio.h>#include<math.h>int primes[168]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997};int main(){ int m,n,i,j,t,count; while(scanf("%d%d",&m,&n)!=EOF) { count=0; if(m<3) { count=1; m=3; } else { if(m%2==0) m++; } for(i=m;i<=n;i+=2) { t=(int)sqrt(i); for(j=0;j<168&&primes[j]<=t;++j) if(i%primes[j]==0) { --count; break; } ++count; } printf("%d\n",count); } return 0;}2、用筛法筛法描述是这样的：从自然数中（1除外）选一个最小的数，你可以大胆宣布它是素数，然后把剩下的所有自然数中是它的倍数的数全部去掉（筛去），接下来从剩下的数中再选一个最小的数重复上面的工作，这样就能求得所有的素数。这个算法最大的弱点是需要比较大的存储空间，而时间复杂性上是比较优的，首先它只做加减法，不用试除，同时设所求范围是(2,n)，那它的复杂度是O(n)，线性复杂度。在设计算法的时候，首先要设一个筛子v[i]，筛子初始为0，如果v[i]==1则表示i不是素数。由于筛子只取0和1，所以可以用一个bit存储。再进一步优化（目的是使存储空间减少），对于偶数的情况不再考虑，筛子中只对奇数进行筛选。代码：#include<stdio.h>#define getmap(x) (bitmap[(x-2)>>4]&bit1[(x/2-1)&7])#define setmap(x) bitmap[(x-2)>>4]|=bit1[(x/2-1)&7]unsigned char bit1[8]={128,64,32,16,8,4,2,1};unsigned char bitmap[62500]={0};int main(){ int i,j,m,n,count; for(i=3;i<=1000000;i+=2) { if(!getmap(i)) { for(j=i+i+i;j<=1000000;j+=(i+i)) setmap(j); } } while(scanf("%d%d",&m,&n)!=EOF) { count=0; if(m<3) { count=1; m=3; } else if(!(m&1)) m++; if(!(n&1)) n--; for(;m<=n;m+=2) if(!getmap(m)) ++count; printf("%d\n",count); } return 0;}
评论