筛法

一，

筛 法 　　筛法，是求不超过自然数N（N＞1）的所有质数的一种方法。据说是古希腊的埃拉托斯特尼 （Eratosthenes，约公元前274～194年）发明的，又称埃拉托斯特尼筛法（sieve of Eratosthenes）。 　　具体做法是：先把N个自然数按次序排列起来。1不是质数，也不是合数，要划去。第二个数2是质 数留下来，而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是 5，把5留下，再把5后面所有能被5整除的数都划去。c这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数。因为希腊人是把 数写在涂腊的板上，每要划去一个数，就在上面记以小点，寻求质数的工作完毕后，这许多小点就像一个筛子，所以就把埃拉托斯特尼的方法叫做“埃拉托斯特尼筛 法”，简称“筛法”。（另一种解释是当时的数写在纸草上，每要划去一个数，就把这个数挖去，寻求质数的工作完毕后，这许多小洞就像一个筛子。） 　　例如，用筛法找出不超过30的一切质数： 　　不超过30的质数2，3，5，7，11，13，17，19，23，29共10个。 　　使用Pascal语言，利用筛法求素数的代码： 　　ReadLn(n);｛需要求2~n之间所有的素数｝ 　　For j:=2 To n Do a[j]:= True;｛全部清成真，表示目前是素数｝ 　　For j:=2 To n Do 　　If a[j] Then｛当该数纪录是质数时开始筛选｝ 　　For i:=2 To n Div j Do a[j*i] := False;｛筛掉所有质数的倍数｝ 　　sum := 0;｛统计范围内有多少个质数｝ 　　For j:=2 To n Do 　　If a[j] Then Begin｛如果是质数就输出｝ 　　Write(j, ' '); 　　Inc(sum); 　　End; 　　WriteLn（sum）;｛输出总数｝ 　　使用C++语言，利用筛法求素数的核心代码： 　　long i,j; 　　bool prime[MAXN]; 　　memset(prime,1,sizeof(prime)); 　　prime[1]=0; 　　for(i=2;i<=n)); j++) 　　{ 　　a[i*p[j]] = 1 ; 　　if (i%p[j] == 0) break; 　　} 　　}


轉帖一下：
http://bbs.pediy.com/showthread.php?t=114593
这里的筛法是说寻找从1到N的所有素数的筛法。不是陈景润先生的那个。。。

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

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

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

程序：

//code by 冬祭
# include 
# include 


# 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 ;
}