这里的筛法是说寻找从1到N的所有素数的筛法。不是陈景润先生的那个。。。

过程：
这两天在逛ACM相关的论坛，发现2007年复旦的xreborner大牛就把筛法改进成线性的时间复杂度了。真是可怕。不知道大家都了解过没，现在介绍给大家。

自己理解了一下，不过觉得与其用文字来表达不如上程序。

想想当初找素数，从2到N每个数字num验证，后来老师告诉我们验证可以只到sqrt(num)，再后来有了筛法，再后来对2的倍数，3的倍数，6的倍数跳过。。。今天，终于有了线性的。。

程序：

//code by 冬祭
# include <stdio.h>
# include <memory.h>

# define N 20 //寻找2到N的所有素数

int main ()
{
        unsigned char P[N + 1] ; //定义一个数组标志位标识是否为素数
        unsigned int Primes[N] ; //存储素数的数组
   
        int Time = 0, Count = 0 ;//算法中的“比较次数、素数个数”

        memset (P, 1, N + 1) ;        //标志全部初始化为1
        memset (Primes, 0, N) ; //初始化素数数组

       
        for (int i = 2; i <= N; i++)
    {
                //若当前i为素数
        if (P[i])
        {
            Primes[Count++] = i ;
            Time++;        //比较一次，次数加一
        }

                //更新素数标志数组
        for (int j = 0; j < Count && i * Primes[j] <= N; j++)
        {
            P[i * Primes[j]] = 0 ;
            Time++;

            if (i % Primes[j] == 0) break;
        }

    }//end for(i)

        printf ("Time = %d\nCount = %d\n\n", Time, Count) ;

        printf ("Primes are :\t") ;
       
        for ( i = 0 ; i < Count ; i++)
                printf ("%d\t", Primes[i]) ;
       
        printf ("\n") ;

        return 0 ;
}

[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入！