用C++編寫的素數判定程序

一、常見的素數判定演算法

素數判定是數論中的基礎問題，一般常用的演算法有：試除法、埃氏篩、線性篩等。

試除法：對於一個數n，從2開始只要能整除n，n就不是素數。

比如259，因為能被7整除，所以不是素數。

這個演算法簡單，容易實現，但是當n很大時，需要進行很多次除法操作，效率比較低。

埃氏篩：將從2開始的所有自然數入列，取出隊首的數p，將p的倍數依次排除，直到隊列為空，則不在這個過程中被篩去的數便是素數。

比如100以內的素數：2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97。

線性篩：試除法的時間複雜度為O($\sqrt n$)，埃氏篩的時間複雜度為O(nloglogn)，而線性篩法的時間複雜度為O(n)。其基本思想是：
如果x是質數，那麼x的倍數一定不是質數；如果x不是質數，那麼x一定是之前某個質數的倍數，它已經在這個質數的篩法中被標記過了。

void get_prime(int n) {
    memset(v, 0, sizeof(v));
    memset(prime, 0, sizeof(prime));
    int cnt = 0;
    for(int i = 2; i <= n; i++) {
        if(v[i] == 0) {
            prime[cnt] = i;
            cnt++;
        }
        for(int j = 0; j < cnt && i * prime[j] <= n; j++) {
            v[i * prime[j]] = 1;
            if(i % prime[j] == 0) break;
        }
    }
}

二、C++的相關語法

C++是一種高級的程序設計語言，它結合了高級語言和低級語言的優點，可以進行高效的系統級編程和高級應用程序開發。下面介紹一些C++常用的語法。

1. 變數：變數是用於存儲值的內存位置。在C++中，變數必須在使用之前被聲明。變數的聲明語法：類型 變數名;

2. if語句：if語句用於在程序中執行不同的動作，根據條件執行不同的代碼塊。if語句的語法：

if(condition) {
    // code if condition is true
}

3. for循環：for循環是一種循環結構，可以重複執行一定的代碼，直到達到指定的次數。for循環的語法：

for(initialization; condition; updation) {
    // code
}

4. 函數：函數是一種獨立的代碼塊，可以被多次調用。在C++中，函數的聲明必須在使用之前。函數的語法：

type function_name(type parameter1, type parameter2,...) {
    // code
    return value;
}

三、基於C++的素數判定程序實例

下面是一個基於C++的素數判定程序實例。這個程序使用了線性篩法來判定素數。

#include 
using namespace std;

const int MAXN = 1000000;

int prime[MAXN], v[MAXN], cnt;

void get_prime(int n) {
    memset(v, 0, sizeof(v));
    memset(prime, 0, sizeof(prime));
    cnt = 0;
    for(int i = 2; i <= n; i++) {
        if(v[i] == 0) {
            prime[cnt] = i;
            cnt++;
        }
        for(int j = 0; j < cnt && i * prime[j] <= n; j++) {
            v[i * prime[j]] = 1;
            if(i % prime[j] == 0) break;
        }
    }
}

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

int main() {
    int x = 37;
    if(is_prime(x)) {
        cout << x << " is a prime number." << endl;
    } else {
        cout << x << " is not a prime number." << endl;
    }
    get_prime(100);
    for(int i = 0; i < cnt; i++) {
        cout << prime[i] << " ";
    }
    cout << endl;
    return 0;
}

四、總結

本文主要介紹了素數判定的常見演算法，包括試除法、埃氏篩和線性篩法。同時，也介紹了C++的一些基本語法以及一個基於C++的素數判定程序實例。對於初學者來說，這些知識是入門必備的。通過學習這些演算法和語法，可以讓我們更好地理解程序設計的本質並提高代碼的效率。