面试问题：递归生成素数的最快方法是什么？
质数的生成很简单但是找到它并以递归方式生成（素数）的最快方法是什么？
这是我的解决方案。 但是，这不是最好的方法。 我认为它是O（N * sqrt（N））。 如果我错了，请纠正我。
public static boolean isPrime(int n) { if (n < 2) { return false; } else if (n % 2 == 0 & n != 2) { return false; } else { return isPrime(n, (int) Math.sqrt(n)); } } private static boolean isPrime(int n, int i) { if (i < 2) { return true; } else if (n % i == 0) { return false; } else { return isPrime(n, --i); } } public static void generatePrimes(int n){ if(n < 2) { return ; } else if(isPrime(n)) { System.out.println(n); } generatePrimes(--n); } public static void main(String[] args) { generatePrimes(200); } 对于recurrsion，你应该使用memoization来改进你的递归函数，意味着如果你找到素数将它保存在数组中，并且在调用isPrime(n)首先检查数字是否存在于数组中，如果不调用isPrime（n，（int） Math.sqrt（N））。 如果isPrime（n，i）返回true，则将其添加到prime列表中，最好将数组排序为二进制搜索，在C＃中有排序列表，并且二进制搜索操作[使n项的列表取O（n log） n）和搜索是O（log（n））]我不知道java [但你可以实现它]。
编辑：您当前的方法是O(n sqrt(n))但是我的approch它可以是相同的顺序！ 但是性能更好，实际上顺序是O(n sqrt(n) / log (n) + n log(n/log(n)))并且因为log（n）小于n^Epsilon ，所以最好说它是O(n sqrt(n))但是你可以看到它会更快地运行log（n）时间。
此外，最好不要i-2，并且在启动时进行一些额外检查以更快地运行算法2 * log（n）时间。
在数学中，Atkin的筛子是一种快速，现代的算法，用于查找指定整数的所有素数。
维基百科文章 （包含伪代码）
为了解决递归问题，也许可以递归地实现Eratosthenes的Sieve 。 此页面可能会有所帮助，因为它似乎讨论了递归实现。
你需要的是Sieve of Forever，这里是一个递归质数测试器的代码，我认为它非常有效，因为它只需要测试素因子，让我知道你的想法;）
顺便说一句，我不会尝试任何超过一个字节的东西，似乎需要一段时间超过100。
public boolean isPrime(byte testNum) { if ( testNum <= 1 ) return false; for ( byte primeFactor = 2; primeFactor < testNum; primeFactor++ ) if ( isPrime(primeFactor) ) if ( testNum % primeFactor == 0 ) return false; return true; }
首先，如果你想生成大素数（而不是测试整数的素数），那么Pocklington定理就派上用场了。 如果你知道足够的p-1素因子，这个定理允许对候选p进行快速素性测试。 因此，以下方法是可能的：生成一些素数，计算其产品的合适倍数并使用Pocklington定理进行测试。 如果要查找大质数（例如，对于RSA密码系统），则必须递归地应用此方法以生成p-1的因子。
上面的描述缺少相当多的细节。 但该方法已经深入分析。 我认为这篇文章是发表时最快的方法，虽然从那时起已经过了一段时间，有人可能已经改进了。
P.Mihailescu。 “使用算术进展中的搜索快速生成可证实的素数”，Proceedings CRYPTO 94，Computer Chactions in Computer Science vol 939，Springer 1994，pp.282-293。
为什么递归？
使用更好的素数生成算法，如Eratosthenes筛选或甚至更好的阿特金筛选。