我有一个蛮力算法,它接受一个输入n,并显示前n个质数代码有效,但我也必须回答这个问题:
给出确保正确性所需的测试项目数量。
有办法计算这个吗?从技术上讲,我是否需要测试所有可能的int值(所有20亿种可能性)?

最佳答案

如果你有一个数字n,并且需要检查它是否是素数,有比暴力更有效的方法。
一种方法是使用Miller-Rabin Primality Test。Miller-Rabin检验要么发现一个数是复合数的证明,要么没有这样的证明(它没有直接证明一个数是素数)所以计划是:
运行miller-rabin最多k次(或者直到它发现这个数字是一个复合数)
如果miller rabin声称它是一个可能的素数,那么执行一个蛮力检查
miller rabin运行as follows。显然,你只需要对奇数n进行测试,所以n-1是偶数,你可以为一些正s和正奇数d写n-1=2sd。从范围(0,n-1)中随机选择a如果ad≠1 n和a2rd≠-1 n,则n是复合的。
如果n是一个组合,miller-rabin的k次迭代不证明它是这样的概率小于4-k。
Miller Rabin的k个应用的计算复杂度,即使是天真的实现,Prime Number theorem,也是O(k Log3(n))。

10-04 19:00