C++判斷質數的實現方法

一、是否為質數的定義

質數是指只能被1和自身整除的正整數。判斷一個數是否為質數，即判斷它能否被除1和自身以外的正整數整除。

二、暴力法判斷質數

暴力法是一種最原始的判斷質數的方法，即對於一個數n，依次判斷2~n-1是否能夠整除n。如果能整除，則認為n不是質數；如果不能整除，則認為n是質數。

bool isPrime(int n) {
    if(n < 2) return false; // 小於2的數不是質數
    for(int i = 2; i < n; i++) {
        if(n % i == 0) return false;
    }
    return true;
}

這種方法的時間複雜度為O(n)，運行時間隨着n的增大而增大，不適用於大數的判斷。需要使用更高效的算法。

三、優化判斷質數的方法

1. 去掉偶數判斷

所有大於2的偶數都不是質數，因為它們都可以被2整除。所以，在判斷一個數是否為質數時，可以先判斷它是否是2，如果是2，則是質數；如果不是2，則去掉偶數進行判斷。

bool isPrime(int n) {
    if(n < 2) return false; // 小於2的數不是質數
    if(n == 2) return true; // 2是質數
    if(n % 2 == 0) return false; // 去掉偶數判斷
    for(int i = 3; i <= sqrt(n); i += 2) { // 只判斷奇數
        if(n % i == 0) return false; 
    }
    return true;
}

在上面的代碼中，倒數第二行中的i += 2是因為質數不可能是偶數，所以可以只判斷奇數。而sqrt(n)的範圍是因為，在2~sqrt(n)之間的數，如果不能整除n，那麼大於sqrt(n)的數也不可能整除n。所以只需要判斷到sqrt(n)。

2. 去掉6的倍數判斷

6的倍數兩側都是偶數，不是質數。在去掉偶數後，如果判斷的數能夠被3整除，那麼它一定不是質數。因為質數只能是6n+1或6n-1的形式，所以只需要判斷6n+1和6n-1的數是否為質數。

bool isPrime(int n) {
    if(n < 2) return false; // 小於2的數不是質數
    if(n == 2 || n == 3) return true; // 2和3是質數
    if(n % 6 != 1 && n % 6 != 5) return false; // 去掉6的倍數判斷
    for(int i = 5; i <= sqrt(n); i += 6) {
        if(n % i == 0 || n % (i + 2) == 0) return false; // 只判斷6n+1和6n-1的數
    }
    return true;
}

四、完整代碼

經過上面的優化，判斷質數的方法已經相對高效了。下面是完整代碼：

#include <iostream>
#include <cmath>
using namespace std;

bool isPrime(int n) {
    if(n < 2) return false; // 小於2的數不是質數
    if(n == 2 || n == 3) return true; // 2和3是質數
    if(n % 6 != 1 && n % 6 != 5) return false; // 去掉6的倍數判斷
    for(int i = 5; i <= sqrt(n); i += 6) {
        if(n % i == 0 || n % (i + 2) == 0) return false; // 只判斷6n+1和6n-1的數
    }
    return true;
}

int main() {
    int n;
    cout << "請輸入一個正整數：" << endl;
    cin >> n;
    if(isPrime(n)) {
        cout << n << "是質數。" << endl;
    } else {
        cout << n << "不是質數。" << endl;
    }
    return 0;
}

五、總結

判斷質數是一項基本的數學問題，同時也是算法領域的一大難題。通過對判斷質數的優化方法的學習和代碼實現，我們可以更好地理解算法中的思想和技巧，同時也能夠增強對基本數據類型的理解。