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)) 有了实质性的改进算法。