篩法求大量素數

一、樸素篩法求n以内的所有素數

原理：如果一個數是合數，那麼我們可以用它的因子（不包括1與它自身）把這個數篩掉。

思路：

         bool f[maxn+100];

         f[i]==1表示數字i不是質數，f[i]==0表示數字i是質數 

         int p[maxn];

         p[0]表示素數的個數，p[i]記錄第i個素數的值  

         我們從2開始往後進行掃描，假設目前掃描到數字 i ，有兩種情況：

          1、f[i]==1，即表示數字 i 為合數，不作處理。

          2、f[i]==0，即表示數字 i 為質數。這是為什麼呢？根據上述原理，若存在數字 j （1<j<i ） 為 i 的因子，那麼在前面枚舉到 j 時，我們會把 j 的所有倍數都标記為合數，也就是說，f[i]==0 就表示在小于 i 的數中，不存在 i 的因子 j ，數字 i 當然也就是質數了。

                ok，接下來還有兩步操作： 

                首先，我們要将素數 i 存儲下來；

                其次，将素數 i 的所有倍數都标記為合數。          

代碼：

f[0]=f[1]=1;
  for(i=2;i<=n;i++)
    if(f[i]==0)
      {
        p[++p[0]]=i;
        for(j=i+i;j<=n;j+=i)f[j]=1;
      }      

二、線性篩法求n以内的素數

原理：每個合數都有一個最小的質因數，每個合數隻被它的最小質因數篩去。

思路：分析上述的樸素篩法，我們可以發現一個數實際上可能被多次篩選，比如數字12，被數字2、3篩選兩次，這就造成效率上的               浪費，有沒有什麼辦法可以使得每個數字都隻被篩選一次，進而使得此篩法成為線性的呢？

            我們可以将樸素篩法進行改進，使得每個數字都隻被它的最小質因數篩去。

            （狀态定義與上面的一緻）

            假設目前枚舉到數字 i ，接下來有兩步處理：

            1、若f[i]==0，即數字 i 為質數，那麼将數字 i 假如素數表p。

            2、此時的話，素數表 p 記憶體儲的都是小于等于 i 的素數。假設第 j  個素數為 p[j] ，則 k =p[j]*i，k的最小質因數即為 p[j]，我們就用 p[j] 篩去數字 k。

                好了，這裡還要講一下的是，下列代碼中的這一句：

                          i f ( i % p [ j ] ==0 ) break;

                為什麼要加這一句呢？若 i % p[j]==0 表示 i 是 p[j] 的倍數，則 k=p[j+1]*i也是 p[j] 倍數，并且可以将其變形得到這樣的一個式                 子：k = p[j+1]*i = p[j+1] * p[j] * x。

                我們的方法是隻用一個數的最小質因數篩去它，由此，p[j] 之後的素數就沒有再枚舉的必要了，而數字p[j] * i 會在之後枚舉                   到數字 p[j+1] * x 時，被  p[j] 篩掉。  

代碼：

int i,j,k,n;
f[0]=f[1]=1;
p[0]=0;
for(i=2;i<=n;i++)
  {
    if(!f[i])p[++p[0]]=i;
    for(j=1;j<=p[0] && i*p[j]<=n;j++)
      {
        f[i*p[j]]=1;
        if(i%p[j]==0)break;
      }
  }      

看了上述的線性篩法，其實還能發現線性求解 n 以内每個數的最小質因數的解法，至于怎麼做，這裡就不再多說了。不知道的話，可以在下方留言。

三、空間折半優化

原理：所有的偶數（除 2 以外）都為合數。

思路：在前面的狀态定義中，我們都是直接存儲數字 i ，用 f[i] 來記錄數字 i 是否為質數。根據上述原理，我們可以隻記錄奇數，而               不記錄偶數，這樣的話，對于給定的範圍 n ，我們原本需要定義長度為 n 的數組，現在僅僅隻用定義長度為 n/2 的數組即可。

            f[i] 記錄數字2*i+1是否為質數，其餘的處理與上述的篩法類似。

加入空間優化之後的代碼：

int i,j,k,n,maxn;
  maxn=n/2;
  p[++p[0]]=2;
  for(i=1;i<=maxn;i++)
    {
      k=2*i+1;  
      if(!f[i])p[++p[0]]=k;
      for(j=2;j<=p[0] && k*p[j]/2<=maxn;j++)
        {
          f[k*p[j]/2]=1;
          if(k%p[j]==0)break;
        }
    }      

四、區間求素數

簡述：有的時候，我們需要知道某個特定區間的素數(區間大小較小，但數可能很大)。

那麼數組就開不下，這時候我們仍然可以使用篩法，隻是所有的下标都進行了偏移。

大家了解下面這段代碼可以先用普通篩法寫，然後數組下标集體移動即可。

const int maxn = 100000;

int PrimeList[maxn];

int PrimeNum;

bool IsNotPrime[maxn]; // IsNotPrime[i] = 1表示i + L這個數是素數.

void SegmentPrime(int L, int U)

{ // 求區間[L, U]中的素數.

int i, j;

int SU = sqrt(1.0 * U);

int d = U - L + 1;

for (i = 0; i < d; i++) IsNotPrime[i] = 0; // 一開始全是素數.

for (i = (L % 2 != 0); i < d; i += 2) IsNotPrime[i] = 1; // 把偶數的直接去掉.

for (i = 3; i <= SU; i += 2)

{

  if (i > L && IsNotPrime[i - L]) continue; // IsNotPrime[i - L] == 1說明i不是素數.

  j = (L / i) * i; // j為i的倍數，且最接近L的數.

  if (j < L) j += i;

if (j == i) j += i; // i為素數，j = i說明j也是素數，是以直接 + i.

j = j - L;

for (; j < d; j += i) IsNotPrime[j] = 1; // 說明j不是素數(IsNotPrime[j - L] = 1).

}

if (L <= 1) IsNotPrime[1 - L] = 1;

if (L <= 2) IsNotPrime[2 - L] = 0;

PrimeNum = 0;

for (i = 0; i < d; i++) if (!IsNotPrime[i]) PrimeList[PrimeNum++] = i + L;

}