素数测试。这个程序比其他程序执行得更快吗？

Question

bool is_prime(BigInt num)
{
    if(num == 0 || num == 1 || (num != 2 && num % 2 == 0))
        return false;

        BigInt sq = sqrt(num);

        for(BigInt i = 3; i <= sq; i += 2)
            if(num % i == 0)
                 return false;

       return true;
}

我们只需要检查平方根。证明 -> https://scienceparv.blogspot.com/2021/07/mathematics-if-one-divisor-of-dividend.html

Answer 1

Is this program performing faster than all others?

没有

有比试验除法更快的素数测试。

例如：

https://en.wikipedia.org/wiki/Elliptic_curve_primality

https://en.wikipedia.org/wiki/Adleman%E2%80%93Pomerance%E2%80%93Rumely_primality_test

另见：https://en.wikipedia.org/wiki/Primality_test

Answer 2

您的代码正在进行所谓的 Trial Division 素性测试，这对于大数字来说很慢。它具有原始操作的时间复杂度 O(Sqrt(N))。

如果您的数字非常大，1024 位或更大，那么 Trial Division 会太慢。

有两种 Primality Tests - 确定性和概率性。 Trial Division 是确定性算法的一个例子。所有确定性算法都比概率算法慢得多。

概率算法永远无法确定一个数是否真的是质数。但是对于任何选择的小概率P，他们可以在非常短的计算时间内判断这个数字是否是这个概率的确定性。确定性算法总是确定一个数是否为质数。

存在比您的确定性素数测试算法更快的算法，例如 Elliptic Curve Primality Test, which is fast but difficult to implement. But you can easily test any number for free with fast software like Primo for Linux，这是免费软件，但源代码封闭且仅适用于 Linux（没有 Windows 版本完全没有）。

我决定从头开始为您实现一个概率素性测试，即 Fermat Primality Test，它非常快速且易于实现，只需几行代码，我在下面的 C++ 代码中就是这样做的。它具有 O(Log2(N)) 的复杂度，即使对于 20000 位数字来说也是非常快的时间。

Try it online!

#include <cstdint>
#include <iostream>

using Word = uint32_t;
using DWord = uint64_t;

Word PowMod(Word a, Word b, Word const & c) {
    // https://en.wikipedia.org/wiki/Modular_exponentiation
    Word r = 1;
    while (b != 0) {
        if (b & 1)
            r = (DWord(r) * a) % c;
        a = (DWord(a) * a) % c;
        b >>= 1;
    }
    return r;
}

Word Rand(Word const & prev, Word const & begin, Word const & end) {
    Word constexpr magic_prime = uint32_t(-1) - 4;
    return Word((DWord(prev) * magic_prime) % (end - begin)) + begin;
}

bool IsFermatProbablePrime(Word const & n, int trials = 32) {
    // https://en.wikipedia.org/wiki/Fermat_primality_test
    if (n <= 16)
        return n == 2 || n == 3 || n == 5 || n == 7 || n == 11 || n == 13;
    Word witness = 2;
    for (size_t i = 0; i < trials; ++i) {
        witness = Rand(witness, 2, n - 2);
        if (PowMod(witness, n - 1, n) != 1)
            return false;
    }
    return true;
}

int main() {
    Word const prime_num = 3941362591U, comp_num = 2245837171U;
    std::cout
        << std::boolalpha
        << "num1 is prime: " << IsFermatProbablePrime(prime_num) << ", "
        << "num2 is prime: " << IsFermatProbablePrime(comp_num)  << std::endl;
}

输出：

num1 is prime: true, num2 is prime: false

（实际上第一个数 prime_num 是质数，第二个 comp_num 是合数）

你可以看到我为 Word 和 DWord 使用了两个 typedef，像这样：

using Word = uint32_t;
using DWord = uint64_t;

这种 typedef 只允许您检查 32 位数字的素数，对于您检查大数字的情况，只需替换为：

using Word = BigInt;
using DWord = BigInt;

使用您已经在代码中使用的 class BigInt。

素数测试。这个程序比其他程序执行得更快吗？

Primality test. Is this program performing faster than all others?

c++

performance

primes