我编写了以下程序,如果数字是质数则返回 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;
}
最佳答案
您可能想看一下 Miller-Rabin primality test .在这个测试中 您使用一系列“见证”值并执行一些计算。每个证人 计算给出“复合”或“可能是素数”的结果。如果你使用 k 个见证人 他们都给出了“可能是素数”的结果,即这个数字实际上是素数的概率 复合是 1/4^k。
运行时间为 O(k log^3 n),这比你的 O(sqrt(n)) 有了实质性的改进 算法。
关于c++ - 我如何提高这种随机素性测试算法的复杂性?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23345592/