伽利略：素数是上帝用来描写宇宙的文字
素数，又称为质数，是不能被1与本身以外的其他整数整除的整数。
求素数的两种方法：
试商判别法筛法试商判别法：应用试商法来探求奇数i（只有唯一偶素数2，不作试商判别）是不是素数，用奇数j（取3,5，…，直到sqrt(i)）去试商。若存在某个j能整除i，说明i能被1与i本身以外的整数j整除，i不是素数。若上述范围内的所有奇数j都不能整除i，则i为素数。
注明：理论上，如果i存在一个大于sqrt(i)且小于i的因数，则必存在一个与之对应的小于sqrt(i)且大于1的因数，因而从判别功能来说，取到sqrt(i)已足够了。
筛法：对于一个大整数x，只要知道不超过sqrt(x)的所有素数p，划去所有p的倍数2p,3p,…,剩下的整数就是不超过x的全部素数。
应用筛选法求素数，为了方便实施“划去”操作，应设置数组。每一数组元素对应一个待判别的奇数，并赋初值0。.如果该奇数为p的倍数则应划去，对应元素加一个划去标记，通常给该元素赋值-1。最后，打印元素值不是-1（即没有划去）的元素对应的奇数即所求素数。在实际应用筛法的过程中，p通常不限于取不超过sqrt(x)的素数，而是适当放宽取不超过sqrt(x)的奇数（从3开始）。这样做尽管多了一些重复划去操作，但程序实现要简便些。
两者比较：试商法较为直观，设计容易实现。筛法在较大整数的判别商效率更高一些，但设计上较难把握。
#include <stdio.h>#include <math.h>void main(){ long int beg,end,g,i,j,k; int count,n;//所有奇数表示为j=beg+2k(k=0,1,...,count) count=(end-beg)/2。于是k=(j-beg)/2是奇数j在数组中的序号 static long int a[11000]; printf("求区间[beg,end]上的素数。\n"); printf("请输入beg,end(c>2):"); scanf("%ld,%ld",&beg,&end); if(beg%2==0) beg++; count=(end-beg)/2;//区间中基数的个数 i=1; while(i<=sqrt(end)) //在[beg,end]中筛选素数 { i=i+2; g=2*(beg/(2*i))+1;//使得gi接近区间下限beg，从而使划去的gi,(g+2)i,...在[beg,end]中，减少无效操作 //以提高对大区间的筛选效率 if(g*i>end) continue; if(g==1) g=3; j=i*g; while(j<=end) { if(j>=beg) a[(j-beg)/2]=-1; j=j+2*i; } } for(n=0,k=0;k<=count;k++) if(a[k]!=-1) { n++; printf("%ld ",beg+2*k); if(n==0) printf ("\n"); } printf ("\n共%d个素数。\n",n);}
转载于:https://www.cnblogs.com/919czzl/p/4020385.html
相关资源：使用Python判断质数(素数)的简单方法讲解