伽利略：素数是上帝用来描写宇宙的文字
素数，又称为质数，是不能被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]上的素数。
");
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%10==0)
printf ("
");
}
printf ("
共%d个素数。
",n);
}