我有一个蛮力算法，它接受一个输入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））。