基本思想：素数的倍数一定不是素数

实现方法：用一个长度为N+1的数组保存信息（0表示素数，1表示非素数），先假设所有的数都是素数（初始化为0），

从第一个素数2开始，把2的倍数都标记为非素数（置为1），一直到大于N；然后进行下一趟，找到2后面的下一个素数3，

进行同样的处理，直到最后，数组中依然为0的数即为素数。

说明：整数1特殊处理即可。

 

#include 
     
      #include 
      
       #include 
       
        int a[100000001];int main(){    int i, j, n;    memset(a, 0, sizeof(a));    while (scanf("%d", &n) != EOF)    {        //n = 100000000;        for (i = 2; i <= n; i++)        {            //如果是素数            if (a[i] == 0)            {                for (j = i + i; j <= n; j += i)                {                    a[j] = 1;                }            }        }        printf("time: %.2lf", (double) clock() / CLOCKS_PER_SEC);        /*        printf("2 ");        for (i = 3; i <= n; i++)        {            if (a[i] == 0)            {                printf("%d ", i);            }        }         */    }    return 0;}
       
      
     

 

 

 

 

优化

#include
     
      #define Max 100000000int a[Max + 1]={
   1,1};int main(){    int i,j;    for(i=4;i<=Max;i+=2)    {        a[i]=1;    }    for(i=3;i*i<=Max;i++)    {        if(!a[i])        {            for(j=3*i;j<=Max;j+=2*i)            {                a[j]=1;            }        }    }    return 0;}