质数表的快速求法

在半年前我写了个质数的筛法。测试时间复杂度是3.3*n而实际上老师的筛法是1.8倍的N当时他的算法我没看懂，老师过多的使用了乘法。而实际上乘法的效率是很低的。今天看懂了。

我室友写了个筛法。

这个是我们之前写的地址

 

我和老师的代码都是冗余在第三层。使用常规筛法如果3的倍数干掉那么3*7*5的值是倍干掉的。但是到了5这里5*3*7又被干掉了一次。这样就造成了冗余。而实际上我是在做乘法的时候只是如果15（被干掉）

我的筛法也有这方面的因素。我的筛的冗余实在第三层。是相邻的比较。相邻的比较是N*N的复杂度固有的特征。如果第三层的是false那么就不去乘以。就继续。这样还是有冗余。去掉的最好方式就是不存在。我的代码第三层如果使用链表解决应该时间复杂度趋近于这个数值。下次测试一下。

# include<stdio.h>
# include<math.h>
# define N 200000000
bool prime[N+1];
int main()
{  int i,j;
long ljq=0;   //记录筛选的次数  当时写成了累加器的缩写.大家更喜欢用count
int cout=1; //记录质数的个数 2走后门， 故初值应设为一
int m=0;//记录i的值，为循环变量的辅助变量
for(i=3;i<=N;i=i+2)//所有的偶数全部干掉
prime[i]=true;
for(i=3;i<=sqrt((N-1));i=i+2)//第一层取平方数
{
    //printf("i=%d/n",i);
     m=i;
     ljq++;
    if(prime[i]==true)

        for(j=i*i;j<=N;j=i*m)//筛法的第二层。从平方开始如果是存在的就筛掉
        {
                m=m+2;
            if(prime[j]==true)
            {
                prime[j]=false;
        //      printf("%d/t",j);//测试用例。用于查看筛掉的数
            }
        }//第二层结束
//printf(   "/n");//测试用例。用于分割筛掉的数。分割间的数之间有相同的差

    }//第一层结束

//printf("/n");

printf("%d/t",2);   /*2非奇数故未在循环算法之内，但2是素数，故先输出*/
//打印质数
for(i=3;i<=N;i=i+2)
if(prime[i]==true)
{
printf("%d/t",i);
cout++;
}
printf("/n");
printf("步长%d",ljq);
printf("/n");
printf("质数的个数%d",cout);

return 0;
}

计算的是2亿的步长196457228两亿的6秒钟。比老师的快了一秒。

不包括打印时间。

时间复杂度不详,筛法的复杂度是Nlog(logN)实际上不到.