前置知識

Cpp實現(xiàn)

基礎(chǔ)算法

// base method
bool basement(int num)
{
	for (int i = 2; i <= sqrt(num); ++i)
	{
		if (num % i == 0)
			return false;
	}
	return true;
}

證明

篩法初步

根據(jù)初等數(shù)學(xué)的知識，如果一個數(shù)不是2的倍數(shù)，那么它肯定不是2的倍數(shù)的倍數(shù)，所以，進一步的我們可以對上面的基礎(chǔ)算法進行優(yōu)化

// sieve first step
bool sieve2Method(int num)
{
	if (num == 2)
		return true;
	if (num % 2 == 0 || num < 2)
		return false;
	else
	{
		for (int i = 3; i * i <= num; i += 2)
		{
			if (num % i == 0)
			{
				return false;
			}
		}
		return true;
	}
}

輪轉(zhuǎn)篩法

6k ± 1 形式 或 輪換篩法（輪轉(zhuǎn)篩法） （Wheel Factorization）。

輪轉(zhuǎn)篩法的基本原理是利用模數(shù)（在這里是6）的性質(zhì)來減少需要檢查的數(shù)。具體到6k ± 1形式，這個形式背后的理由如下：

• 整數(shù) n 可以表示為 6?+?，其中 ? 是0到5之間的一個整數(shù)。
• 對于 ?=0,2,3,4，這些數(shù)都可以被2或3整除（即它們是合數(shù)）。
• 只有 ?=1 和 ?=5（即 6?+1 和 6??1）可能是質(zhì)數(shù)。

bool isPrime_3(int num)
{
	if (num == 2 || num == 3)
		return 1;
	// 不在6的倍數(shù)兩側(cè)的一定不是質(zhì)數(shù)
	if (num % 6 != 1 && num % 6 != 5)
		return 0;
	int tmp = sqrt(num);
	// 在6的倍數(shù)兩側(cè)的也可能不是質(zhì)數(shù)
	for (int i = 5; i <= tmp; i += 6)
		if (num % i == 0 || num % (i + 2) == 0)
			return 0;
	// 排除所有，剩余的是質(zhì)數(shù)
	return 1;
}

埃拉托斯特尼篩法生成素數(shù)表

根據(jù)上面我們的初步想法，我們可以進一步的將用于篩選的因子擴大。
但是，這種篩法的核心思想之一是：
如何確定篩選因子 ？
既然我們要做到高效，那么這些篩選因子之間的篩取最好沒有重合，或者重合度很小，至少它不應(yīng)該完全重復(fù)篩取，對吧？
考慮2,3,4這三個數(shù)。
經(jīng)過簡單運算，我們知道將3作為篩選因子，是可以篩取到2曬不出的數(shù)字的，比如說9，但是4，因為它有因子2，所以它所有篩取的數(shù)字，均早就被2篩取過了。
所以，我們應(yīng)該選取素數(shù)作為篩取因子。

std::vector sieveOfEratosthenes(int n)
{
	std::vector isPrime(n + 1, true);
	isPrime[0] = isPrime[1] = false; // 0和1不是素數(shù)

	for (int p = 2; p <= std::sqrt(n); ++p)
	{
		if (isPrime[p])
		{
			for (int i = p * p; i <= n; i += p)
			{
				isPrime[i] = false;
			}
		}
	}
	return isPrime;
}

但是這里面還有一些實現(xiàn)細節(jié)，需要注意：

• 初始化0 1 索引為false，
• p <= sqrt(n)
• i = p * p

我們一個個來說，1 略
2 為什么p<=sqrt(n)，這樣可以篩全嗎？
是可以的，首先我們初始化值為false，這意味著我們只需要篩選出 1 ~ n中的合數(shù)即可。
又根據(jù)我們上面對于 基本方法的循環(huán)范圍的證明 ，所以，只要一個數(shù)是合數(shù)，那么它肯定會在2~ $\sqrt{ n }$ 之間
所以，我們可以通過反向推導(dǎo)，如果某一個因子，能夠通過倍加自己，或者可以理解為以自己為步長進行步進， 那么他肯定能夠到達那些以它為因子的合數(shù)位置上 。

3 為什么 內(nèi)層的i要初始化為 $p * p$ ,而不是 $p * 2$之類的
這是因為要防止和之前已經(jīng)篩過的部分發(fā)生重合，比如3個2和2個3

歐拉篩法

從上面埃氏篩法，我們確立了可以通過篩取合數(shù)，從而反向獲取素數(shù)的思路。但顯然，它仍有優(yōu)化的空間，那就是重復(fù)的篩取。而歐拉篩法正為此而生。

歐拉篩，又稱線性篩，時間復(fù)雜度只有O(n)

在埃氏篩法的基礎(chǔ)上，讓每一個合數(shù)都只被它的最小質(zhì)因子篩選一次，以達到不重復(fù)篩選的目的，大大地節(jié)省了時間，從埃氏篩的O(n2)降到O(n)級別

我們想要阻止重復(fù)標記的發(fā)生，就需要一種規(guī)則，也就是說只讓標記以某一種特定的形式or規(guī)律被標記，在歐拉篩法中，這表現(xiàn)為，只用最小素因子去標記

為了知道最小素因子， 我們很自然地需要一個表維護已知的素數(shù)

歐拉篩法正確性的證明

實現(xiàn)

vector eulerSieve(int n)
{
	std::vector isPrime(n + 1, true);
	std::vector primes;         // 素數(shù)集合
	isPrime[0] = isPrime[1] = false; // 0和1不是素數(shù)

	for (int i = 2; i <= n; ++i)
	{
		if (isPrime[i])
		{
			primes.push_back(i);
		}
		for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j)
		{
			isPrime[i * primes[j]] = false;
			if (i % primes[j] == 0)
				break;
		}
	}
	return primes;
}

Miller-Rabin算法。
暫時不看~

Miller-Rabin算法

Miller-Rabin算法是一種概率性質(zhì)數(shù)測試算法，可以用來判斷一個大整數(shù)是否為質(zhì)數(shù)。該算法基于數(shù)論中的一些深刻性質(zhì)，其優(yōu)點在于對大數(shù)的判斷效率非常高。雖然它是一個概率算法，但通過多次測試，可以將錯誤率降到非常低。

Miller-Rabin算法步驟

Miller-Rabin算法基于Fermat小定理以及以下兩個重要的數(shù)學(xué)性質(zhì)：

1. 如果 ? 是一個質(zhì)數(shù)，則對于任何整數(shù) ? 滿足 $1≤?≤??1$，有 $?^{n-1} ≡ 1 mod???$。
2. 如果 ? 是一個奇質(zhì)數(shù)，則存在一個唯一的表達式 $??1=2^{s}??$，其中 ? 是一個奇數(shù)，$?≥1$。

具體步驟

1. 將 ??1 表示為 $2^{s}??$:

   • 例如，對于 ?=15n=15，我們有 ??1=14n?1=14，即 14=2?714=2?7，這里 ?=7d=7 和 ?=1s=1。

2. 隨機選擇一個整數(shù) ? 其中$1 \le a \le n-1$

   • 如果存在 $??≡1mod???$，則 ?n 可能是一個質(zhì)數(shù)。
   • 對于 ?=0,1,…,??1，如果存在 $? ^{2 ???}≡?1mod???$，則 ? 可能是一個質(zhì)數(shù)。

3. 重復(fù)上述測試 k 次:

   • 選擇不同的 ? 進行多次測試。
   • 如果所有測試均通過，則 ? 很可能是一個質(zhì)數(shù)。
   • 如果有一次測試失敗，則 ? 不是質(zhì)數(shù)。

Miller-Rabin算法的偽代碼

#include 
#include 
#include 

// 使用快速冪算法計算 (base^exponent) % mod
long long mod_exp(long long base, long long exponent, long long mod) {
    long long result = 1;
    base = base % mod;
    while (exponent > 0) {
        if (exponent % 2 == 1) {
            result = (result * base) % mod;
        }
        exponent = exponent >> 1;
        base = (base * base) % mod;
    }
    return result;
}

// Miller-Rabin測試的核心函數(shù)
bool miller_test(long long d, long long n) {
    long long a = 2 + rand() % (n - 4); // 隨機選擇 2 <= a <= n-2
    long long x = mod_exp(a, d, n);

    if (x == 1 || x == n - 1) {
        return true;
    }

    while (d != n - 1) {
        x = (x * x) % n;
        d *= 2;

        if (x == 1) {
            return false;
        }
        if (x == n - 1) {
            return true;
        }
    }
    return false;
}

// Miller-Rabin 素性測試
bool is_prime(long long n, int k) {
    if (n <= 1 || n == 4) {
        return false;
    }
    if (n <= 3) {
        return true;
    }

    // 將 n-1 表示為 2^s * d
    long long d = n - 1;
    while (d % 2 == 0) {
        d /= 2;
    }

    // 進行 k 次測試
    for (int i = 0; i < k; i++) {
        if (!miller_test(d, n)) {
            return false;
        }
    }
    return true;
}

int main() {
    srand(time(0)); // 初始化隨機數(shù)生成器

    long long n;
    int k = 5; // 測試次數(shù)
    std::cout << "Enter a number to check if it is prime: ";
    std::cin >> n;

    if (is_prime(n, k)) {
        std::cout << n << " is a prime number." << std::endl;
    } else {
        std::cout << n << " is not a prime number." << std::endl;
    }

    return 0;
}

代碼解析

1. 快速冪算法 ： mod_exp 函數(shù)用于計算 (????????????)mod?????(baseexponent)modmod，以高效地進行大數(shù)冪運算。
2. Miller-Rabin測試的核心函數(shù) ： miller_test 函數(shù)進行一次Miller-Rabin測試，通過隨機選擇基數(shù) ? 并進行多次平方檢驗來判斷 ? 是否可能是質(zhì)數(shù)。
3. 素性測試函數(shù) ： is_prime 函數(shù)調(diào)用 miller_test 函數(shù)進行多次測試，以概率性的方式判斷 ?n 是否為質(zhì)數(shù)。

Miller-Rabin算法的優(yōu)點

• 高效 ：對于大數(shù)，Miller-Rabin測試比許多其他算法更高效。
• 可調(diào)性 ：通過增加測試次數(shù) ?，可以降低誤判率，使得算法在實際應(yīng)用中非�？煽�。