前置知識(shí)

Cpp實(shí)現(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í)，如果一個(gè)數(shù)不是2的倍數(shù)，那么它肯定不是2的倍數(shù)的倍數(shù)，所以，進(jìn)一步的我們可以對(duì)上面的基礎(chǔ)算法進(jìn)行優(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ì)來(lái)減少需要檢查的數(shù)。具體到6k ± 1形式，這個(gè)形式背后的理由如下：

• 整數(shù) n 可以表示為 6?+?，其中 ? 是0到5之間的一個(gè)整數(shù)。
• 對(duì)于 ?=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;
}

埃拉托斯特尼篩法生成素?cái)?shù)表

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

std::vector sieveOfEratosthenes(int n)
{
	std::vector isPrime(n + 1, true);
	isPrime[0] = isPrime[1] = false; // 0和1不是素?cái)?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;
}

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

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

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

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

歐拉篩法

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

歐拉篩，又稱(chēng)線(xiàn)性篩，時(shí)間復(fù)雜度只有O(n)

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

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

為了知道最小素因子， 我們很自然地需要一個(gè)表維護(hù)已知的素?cái)?shù)

歐拉篩法正確性的證明

實(shí)現(xiàn)

vector eulerSieve(int n)
{
	std::vector isPrime(n + 1, true);
	std::vector primes;         // 素?cái)?shù)集合
	isPrime[0] = isPrime[1] = false; // 0和1不是素?cái)?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算法。
暫時(shí)不看~

Miller-Rabin算法

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

Miller-Rabin算法步驟

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

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

具體步驟

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

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

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

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

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

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

Miller-Rabin算法的偽代碼

#include 
#include 
#include 

// 使用快速冪算法計(jì)算 (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測(cè)試的核心函數(shù)
bool miller_test(long long d, long long n) {
    long long a = 2 + rand() % (n - 4); // 隨機(jī)選擇 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 素性測(cè)試
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;
    }

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

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

    long long n;
    int k = 5; // 測(cè)試次數(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ù)用于計(jì)算 (????????????)mod?????(baseexponent)modmod，以高效地進(jìn)行大數(shù)冪運(yùn)算。
2. Miller-Rabin測(cè)試的核心函數(shù) ： miller_test 函數(shù)進(jìn)行一次Miller-Rabin測(cè)試，通過(guò)隨機(jī)選擇基數(shù) ? 并進(jìn)行多次平方檢驗(yàn)來(lái)判斷 ? 是否可能是質(zhì)數(shù)。
3. 素性測(cè)試函數(shù) ： is_prime 函數(shù)調(diào)用 miller_test 函數(shù)進(jìn)行多次測(cè)試，以概率性的方式判斷 ?n 是否為質(zhì)數(shù)。

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

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