素数筛法

1,埃拉托斯特尼筛法

int i,j,k;

for(int i=2;i<=n;i++)u[i]=true;  //初始时所有数都在筛中

for(int i=2;i<=n;i++)                 //顺序搜索筛中的最小的数

     if(u[i]){

            for(int j=2;j*i<=n;j++) //将i的倍数从筛中筛去

                         u[i*j]=false;

      }

for(int i=2;i<=n;i++)  //将筛中的所有数都放入su中

    if(u[i]){

    su[++num]=i;

}

2，欧拉筛法     O（n）

（每个合数仅被它最小的质因数筛去）

int  i,j,num=1;

memset(u,true,sizeof(u));

for(i=2;i<=n;i++) {                 //顺序分析整数区间的每一个数

     if（u[i]）su[num++]=i;     //将筛中最小数送入素数表

     for(j=1;j<num;j++) {           //搜索素数表中的每一个数

            if(i*su[j]>n)break;       //若i与当前素数的乘积超出范围，则分析下一个整数i

            u[ i*su[j] ]=false;         //将i与当前素数的乘积从筛中筛去

            if(i%su[j]==0)break;   //若当前素数为i的最小因子，则分析下一个整数

}

}