面试问题：递归生成质数的最快方法是什么？

面试问题：递归生成质数的最快方法是什么？

对于递归，您应该使用 记忆
来改善递归功能，这意味着如果找到素数将其保存在数组中，并且在

isPrime(n)

未调用isPrime（n，（int）Math.sqrt（
n））。同样，如果isPrime（n，i）返回true，将其添加到素数列表中，则最好对数组进行排序以进行二进制搜索，在C＃中有一个排序列表，然后进行二进制搜索 *** 作[使n个项目的列表取O（n
log n）并且搜索是O（log（n））]我不知道Java [但是您可以实现]。

编辑： 您当前的方法是，

O(n sqrt(n))

但按照我的要求，它可以按相同顺序排列！但是性能更好，实际上顺序是这样的，

O(n sqrt(n)/ log (n) + n log(n/log(n)))

并且因为log（n）小于

n^Epsilon

，所以最好这样说，

O(nsqrt(n))

但是如您所见，它将以更快的速度运行log（n）。

同样最好是i-2不是i-并在启动时进行一些额外的检查以更快地运行算法2 * log（n）。