對于線性時間篩選素數算法的了解

1. 算法描述

線性篩選素數和其它的素數篩選方法比如Eratosthenes篩選都是一個思想，就是在已篩選出來的素數基礎上按倍數把後面的合數去掉，但是由于多了下面這麼一個判斷一下子變成了線性時間複雜度。

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

2. 算法實作

#include <stdio.h>
#define N 100000
/* 打出一張素數表和一張判斷表 */
void primeTable(int *prime, int *isPrime)
{
    int pnum = , i, j;
    for(i=; i<=N; i++)
        isPrime[i] = ;
    for(i=; i<=N; i++)
    {
        if(isPrime[i]==)
            prime[pnum++] = i;
        for(j=; j<pnum && prime[j]*i<=N; j++)
        {
            isPrime[prime[j]*i] = ;
            if(i%prime[j]==)
                break;
        }
    }
}
int main()
{
    int n, prime[N+], isPrime[N+];
    printf("請輸入一個整數: ");
    scanf("%d", &n);
    primeTable(prime, isPrime);

    if(isPrime[n]==)
        printf("是素數\n");
    else
        printf("不是素數\n");
    return ;
}
           

3. 主要解釋if(i%prime[j]==0) break;

關于這一句的解釋一搜一大堆，無非都是兩個數相乘可以由一個更小的質數和一個更大的合數相乘得到，這不需要什麼理論應該可以感覺出來，比如4*6=3*8=2*12，但是問題是為什麼當i能夠整除素數表中目前的素數時，就不用再使用下一個素數去篩掉後面的合數。

假設目前素數表為:2 3

而此時i為4，

在标記完2*4=8為合數之後，判斷出4能夠整除2，按照算法此時應該不用管3了，而是直接i++之後素數表從頭開始與i相乘标記後面的合數。

分析一下，既然i為4能夠整除2，那麼i的倍數肯定也能整除2（這是理所當然的），比如下一個素數3，也就是說有下面的等式

目前i *  == X *     （X表示某個數，因為<,是以X>目前i）
           

而i不斷遞增總有一天會等于X,是以

目前i *  == 未來i * 
           

是以目前的i不要去急着去把未來的事給做了，等将來i由4遞增變成了6，就可以去完成這一步将12給标記為合數了，否則會導緻重複運算一次。

同理，當素數表為:2 3 5 7

目前i=9時，

isPrime[9*2] = isPrime[18] = 0

isPrime[9*3] = isPrime[27] = 0

此時9 % 3 == 0，如果現在把5*9=45給做了的話，根據

目前i *  = 未來i * 
           

當i遞增到15時，又會重複運算一遍，這樣就達不到線性時間了。