用不同的方法求素數

素數是指只能被1和自身整除的正整數，如2、3、5、7、11、13等。素數在密碼學、計算機科學、數學、物理等領域都有着廣泛的應用。本文將介紹幾種常見的求素數的方法，包括暴力枚舉法、埃拉托色尼篩法、線性篩法等。

一、暴力枚舉法

暴力枚舉法是指對於每一個需要判斷的數，都分別除以2到它的平方根之間的每個數，如果都不能整除，則該數是素數。雖然這種方法容易實現，但對於大數，其時間複雜度過高。

bool isPrime(int n){
    if(n<=1)
        return false;
    for(int i=2;i*i<=n;i++){
        if(n%i==0)
            return false;
    }
    return true;
}

二、埃拉托色尼篩法

埃拉托色尼篩法，也稱質數篩，是一種用來篩選素數的算法。其基本思想是從小到大依次枚舉整數，如果它是質數，則將其倍數全部標記為合數。

void sieve(int n){
    bool prime[n + 1];
    memset(prime, true, sizeof(prime));

    for(int p = 2; p * p <= n; p++){
        if(prime[p] == true){
            for(int i = p * 2; i <= n; i += p)
                prime[i] = false;
        }
    }

    for(int p = 2; p <= n; p++){
        if(prime[p])
            cout << p << " ";
    }
}

三、線性篩法

線性篩法，又稱歐拉篩法，是對於埃拉托色尼篩法的優化，其主要思想是將每個合數僅被它的最小質數篩去，而不被多次標記。這樣使得每個數僅會被標記一次，時間複雜度為O(n)。

void sieve(int n){
    bool prime[n + 1];
    memset(prime, true, sizeof(prime));

    for(int i = 2; i <= n; i++){
        if(prime[i] == true)
            cout << i << " ";
        for(int j = 2; j <= n/i; j++){
            prime[i * j] = false;
            if(j >= i)
                break;
        }
    }
}

四、小結

不同的方法對於求解素數都有着各自的優缺點。暴力枚舉法適用於小數據範圍，但在大數據下時間複雜度過高；埃拉托色尼篩法從概念上較為直觀，但空間複雜度較高；線性篩法則是上述算法的優化。在實踐中，我們可以根據數據量的大小和對算法的要求，選擇合適的方法來求解素數。