c++ - 如何提高这种随机素性测试算法的复杂性？

Question

我编写了以下程序，如果一个数字是素数，则返回 1，如果它是合数，则返回 0。虽然有可能错误地将复合物识别为素数。我想要关于改进（降低）以下算法的时间复杂度的建议。

int compute(int n)
{
    int x;
    for(int i = 1; i < 100 * sqrt(n); i++)
    {
        x = rand() % ((int)sqrt(n) + 1);
        if(x != 0 && x != 1 && x!=n)
        {
            if(n % x == 0)
            return 0;
        }
    }
    return 1;
}

Answer 1

您可能想看看Miller-Rabin primality test。在此测试中，您使用一系列“见证”值并执行一些计算。每个见证计算都会给出“复合”或“可能是素数”的结果。如果您使用 k 个见证人并且它们都给出“可能是素数”的结果，那么这个数字实际上是复合的概率是 1/4^k。

运行时间为 O(k log^3 n)，这是对 O(sqrt(n)) 算法的重大改进。