C++判斷質數的方法

一、什麼是質數

質數（素數）指除了1和它本身外，不能被其他數整除的自然數。例如，2、3、5、7、11、13等都是質數。

二、方法一：暴力枚舉法

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

這是最常見的判斷質數的方法之一。從2開始循環遍歷到n-1，如果n能被i整除，說明n不是質數。

雖然時間複雜度為O(n)，但是對於小範圍的數，這種方法是可行的。

三、方法二：開方法

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

對於大範圍的數，暴力枚舉法的時間複雜度會很高，我們可以使用開方的方法來減少循環的次數。

一個數若有大於sqrt(n)的因子，那麼一定有小於sqrt(n)的因子。因此，在循環條件中使用sqr = sqrt(n)，可以減少循環的次數。

四、方法三：質數判定定理

質數判定定理是一個重要的數學定理，它能夠判斷一個很大的數是否為質數。

根據費馬小定理，如果p是質數，a是不是p的倍數，那麼a的p-1次方除以p的餘數一定是1。

long long pow_mod(long long a, long long b, long long p) {
    long long ans = 1 % p;
    for (; b; b >>= 1, a = (a * a) % p) {
        if (b & 1) {
            ans = (ans * a) % p;
        }
    }
    return ans;
}

bool isPrime(int n) {
    if (n == 2 || n == 3 || n == 5 || n == 7) {
        return true;
    }
    if (n == 1 || n % 2 == 0 || n % 3 == 0 || n % 5 == 0 || n % 7 == 0) {
        return false;
    }
    long long a[5] = {2, 3, 5, 7, 11};
    long long d = n - 1;
    int s = 0;
    while (d % 2 == 0) {
        ++s;
        d >>= 1;
    }
    for (int i = 0; i < 5; ++i) {
        if (n == a[i]) {
            return true;
        }
        long long t = pow_mod(a[i], d, n);
        if (t == 1) {
            continue;
        }
        for (int j = 0; j < s; ++j) {
            if (t == n - 1) {
                break;
            }
            t = (t * t) % n;
        }
        if (t != n - 1) {
            return false;
        }
    }
    return true;
}

這個算法的時間複雜度是O(klog³n)，其中k是測試次數，一般取15~20之間的數即可。

五、方法四：線性篩法

線性篩法不僅可以判斷質數，還可以預處理出小於等於n的所有素數。

bool prime[N + 5];
int primes[N + 5], cnt = 0;

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

該算法的時間複雜度為O(n)。

六、方法五：Miller-Rabin算法

Miller-Rabin算法是一種更加高效的質數判定算法，它可以在O(klog³n)的時間複雜度內完成，其中k是測試次數。

long long mul(long long a, long long b, long long mod) {
    long long ans = 0;
    for (; b; b >>= 1, a = (a + a) % mod) {
        if (b & 1) {
            ans = (ans + a) % mod;
        }
    }
    return ans;
}

long long pow_mod(long long a, long long b, long long mod) {
    long long ans = 1 % mod;
    a %= mod;
    for (; b; b >>= 1, a = mul(a, a, mod)) {
        if (b & 1) {
            ans = mul(ans, a, mod);
        }
    }
    return ans;
}

bool Miller_Rabin(long long n) {
    if (n >= 1;
    }
    for (int i = 0; i < 8; ++i) {
        long long a = rand() % (n - 2) + 2;
        long long x = pow_mod(a, d, n);
        long long y = 0;
        for (int j = 0; j < d; j++, x = y) {
            y = mul(x, x, n);
            if (y == 1 && x != 1 && x != n - 1) {
                return false;
            }
        }
        if (y != 1) {
            return false;
        }
    }
    return true;
}

這個算法利用費馬小定理和歐拉定理，隨機選擇一個整數a，通過a^d % n與n來判斷n是否為質數。

七、總結

本文介紹了5種判斷質數的算法，分別是暴力枚舉法、開方法、質數判定定理、線性篩法和Miller-Rabin算法。不同的算法適用於不同大小的數，選擇合適的算法可以減少時間複雜度，提高程序效率。