小编点评

**p * p$ 的目的是为了防止和之前已经筛过的部分发生重合，比如 3 个 2 和 2 个 3 欧拉筛法从上面埃氏筛法，我们确立了可以通过筛取合数，从而反向获取素数的思路。** **欧拉筛法是通过只使用最小素因子标记合数的方法实现素数检测的算法。** ** Miller-Rabin 算法是概率性质数测试算法，可以用来判断一个大整数是否为质数。** ** Miller-Rabin 算法的基本原理是基于以下两个重要数学性质：** * 如果𝑛是质数，则对于任何整数𝑎满足 1 ≤𝑎 ≤𝑛 - 1，有 a^{n - 1} ≡ 1 mod n。 * 如果𝑛是奇质数，则存在一个唯一的表达式 n - 1 = 2^s * d，其中 d 是一个奇数，s ≥ 1。 ** Miller-Rabin 算法的步骤如下：** 1. 选择一个随机整数 a 其中 1 ≤ a ≤ n - 1。 2. 计算 x = mod_exp(a, d, n) ，其中 d 是 n - 1。 3. 如果 x == 1 或 x == n - 1，则 n 是一个质数。 4. 如果 x 不等于 1，则不断乘 x 以计算 x 的平方。 5. 如果 x == 1，则 n 不是质数。 6. 如果 x == n - 1，则 n 是一个质数。 ** Miller-Rabin 算法的优点是：** * 效率高，对于大数，比其他算法更有效。 * 可调性，可以根据需要调整测试次数。

正文

前置知识

Cpp实现

基础算法

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

证明

筛法初步

根据初等数学的知识，如果一个数不是2的倍数，那么它肯定不是2的倍数的倍数，所以，进一步的我们可以对上面的基础算法进行优化

// 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;
	}
}

轮转筛法

6k ± 1 形式 或 轮换筛法（轮转筛法）（Wheel Factorization）。

轮转筛法的基本原理是利用模数（在这里是6）的性质来减少需要检查的数。具体到6k ± 1形式，这个形式背后的理由如下：

• 整数 n 可以表示为 6𝑘+𝑟，其中 𝑟 是0到5之间的一个整数。
• 对于 𝑟=0,2,3,4，这些数都可以被2或3整除（即它们是合数）。
• 只有 𝑟=1 和 𝑟=5（即 6𝑘+1 和 6𝑘−1）可能是质数。

bool isPrime_3(int num)
{
	if (num == 2 || num == 3)
		return 1;
	// 不在6的倍数两侧的一定不是质数
	if (num % 6 != 1 && num % 6 != 5)
		return 0;
	int tmp = sqrt(num);
	// 在6的倍数两侧的也可能不是质数
	for (int i = 5; i <= tmp; i += 6)
		if (num % i == 0 || num % (i + 2) == 0)
			return 0;
	// 排除所有，剩余的是质数
	return 1;
}

埃拉托斯特尼筛法生成素数表

根据上面我们的初步想法，我们可以进一步的将用于筛选的因子扩大。
但是，这种筛法的核心思想之一是：
如何确定筛选因子？
既然我们要做到高效，那么这些筛选因子之间的筛取最好没有重合，或者重合度很小，至少它不应该完全重复筛取，对吧？
考虑2,3,4这三个数。
经过简单运算，我们知道将3作为筛选因子，是可以筛取到2晒不出的数字的，比如说9，但是4，因为它有因子2，所以它所有筛取的数字，均早就被2筛取过了。
所以，我们应该选取素数作为筛取因子。

std::vector<bool> sieveOfEratosthenes(int n)
{
	std::vector<bool> isPrime(n + 1, true);
	isPrime[0] = isPrime[1] = false; // 0和1不是素数

	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;
}

但是这里面还有一些实现细节，需要注意：

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

我们一个个来说，1 略
2 为什么p<=sqrt(n)，这样可以筛全吗？
是可以的，首先我们初始化值为false，这意味着我们只需要筛选出 1 ~ n中的合数即可。
又根据我们上面对于基本方法的循环范围的证明，所以，只要一个数是合数，那么它肯定会在2~ $\sqrt{ n }$ 之间
所以，我们可以通过反向推导，如果某一个因子，能够通过倍加自己，或者可以理解为以自己为步长进行步进，那么他肯定能够到达那些以它为因子的合数位置上。

3 为什么 内层的i要初始化为 $p * p$ ,而不是 $p * 2$之类的
这是因为要防止和之前已经筛过的部分发生重合，比如3个2和2个3

欧拉筛法

从上面埃氏筛法，我们确立了可以通过筛取合数，从而反向获取素数的思路。但显然，它仍有优化的空间，那就是重复的筛取。而欧拉筛法正为此而生。

欧拉筛，又称线性筛，时间复杂度只有O(n)

在埃氏筛法的基础上，让每一个合数都只被它的最小质因子筛选一次，以达到不重复筛选的目的，大大地节省了时间，从埃氏筛的O(n2)降到O(n)级别

我们想要阻止重复标记的发生，就需要一种规则，也就是说只让标记以某一种特定的形式or规律被标记，在欧拉筛法中，这表现为，只用最小素因子去标记

为了知道最小素因子，我们很自然地需要一个表维护已知的素数

欧拉筛法正确性的证明

实现

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

	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算法是一种概率性质数测试算法，可以用来判断一个大整数是否为质数。该算法基于数论中的一些深刻性质，其优点在于对大数的判断效率非常高。虽然它是一个概率算法，但通过多次测试，可以将错误率降到非常低。

Miller-Rabin算法步骤

Miller-Rabin算法基于Fermat小定理以及以下两个重要的数学性质：

1. 如果 𝑛 是一个质数，则对于任何整数 𝑎 满足 $1≤𝑎≤𝑛−1$，有 $𝑎^{n-1} ≡ 1 mod  𝑛$。
2. 如果 𝑛 是一个奇质数，则存在一个唯一的表达式 $𝑛−1=2^{s}⋅𝑑$，其中 𝑑 是一个奇数，$𝑠≥1$。

具体步骤

1. 将 𝑛−1 表示为 $2^{s}⋅𝑑$:

   • 例如，对于 𝑛=15n=15，我们有 𝑛−1=14n−1=14，即 14=2⋅714=2⋅7，这里 𝑑=7d=7 和 𝑠=1s=1。

2. 随机选择一个整数 𝑎 其中$1 \le a \le n-1$

   • 如果存在 $𝑎𝑑≡1mod  𝑛$，则 𝑛n 可能是一个质数。
   • 对于 𝑗=0,1,…,𝑠−1，如果存在 $𝑎^{2𝑗⋅𝑑}≡−1mod  𝑛$，则 𝑛 可能是一个质数。

3. 重复上述测试 k 次:

   • 选择不同的 𝑎 进行多次测试。
   • 如果所有测试均通过，则 𝑛 很可能是一个质数。
   • 如果有一次测试失败，则 𝑛 不是质数。

Miller-Rabin算法的伪代码

#include <iostream>
#include <cstdlib>
#include <ctime>

// 使用快速幂算法计算 (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测试的核心函数
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)); // 初始化随机数生成器

    long long n;
    int k = 5; // 测试次数
    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函数用于计算 (𝑏𝑎𝑠𝑒𝑒𝑥𝑝𝑜𝑛𝑒𝑛𝑡)mod  𝑚𝑜𝑑(baseexponent)modmod，以高效地进行大数幂运算。
2. Miller-Rabin测试的核心函数：miller_test函数进行一次Miller-Rabin测试，通过随机选择基数 𝑎 并进行多次平方检验来判断 𝑛 是否可能是质数。
3. 素性测试函数：is_prime函数调用 miller_test 函数进行多次测试，以概率性的方式判断 𝑛n 是否为质数。

Miller-Rabin算法的优点

• 高效：对于大数，Miller-Rabin测试比许多其他算法更高效。
• 可调性：通过增加测试次数 𝑘，可以降低误判率，使得算法在实际应用中非常可靠。