java 面试问题：递归生成素数的最快方法是什么？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4551731/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Interview question : What is the fastest way to generate prime number recursively?
提问by
Generation of prime number is simple but what is the fastest way to find it and generate( prime numbers) it recursively ?
素数的生成很简单，但是找到它并递归生成（素数）的最快方法是什么？
Here is my solution. However, it is not the best way. I think it is O(N*sqrt(N)). Please correct me, if I am wrong.
这是我的解决方案。然而，这并不是最好的方法。我认为它是 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);
}
采纳答案by Saeed Amiri
For recurrsion, You should use memoizationto improve your recursive function, means if you finding prime number save it in array, and in call to isPrime(n)first check the number exists in array if not call to isPrime(n, (int) Math.sqrt(n)). also if isPrime(n,i) returns true, add it to prime list, it's better your array be sorted to do binary search, in C# there is sorted list, and binary search operation [making list of n item takes O(n log n) and searching is O(log(n))] i didn't know about java [but you can implement it].
对于递归，您应该使用memoization来改进您的递归函数，这意味着如果您找到素数将其保存在数组中，并在调用时isPrime(n)首先检查数组中是否存在数如果不调用 isPrime(n, (int) Math.sqrt( n))。此外，如果 isPrime(n,i) 返回 true，则将其添加到素数列表中，最好对数组进行排序以进行二分查找，在 C# 中有排序列表和二分查找操作 [制作 n 项列表需要 O(n log n) 并且搜索是 O(log(n))] 我不知道 java [但你可以实现它]。
Edit:your current approach is O(n sqrt(n))but with my approch it can be in same order! but better performance, in fact the order is O(n sqrt(n) / log (n) + n log(n/log(n)))and because log(n) is smaller then n^Epsilon, it's better to say it's O(n sqrt(n))but as you can see it will run log(n) time faster.
编辑：你目前的方法是，O(n sqrt(n))但我的方法可以按相同的顺序！但更好的性能，实际上顺序是O(n sqrt(n) / log (n) + n log(n/log(n)))并且因为 log(n) 更小n^Epsilon，所以最好说它是，O(n sqrt(n))但正如你所看到的，它会更快地运行 log(n) 时间。
Also it's better do i-2 not i-- and some extra check in startup to run algorithm 2*log(n) time faster.
此外，最好执行 i-2 而不是 i-- 并在启动时进行一些额外检查以更快地运行算法 2*log(n) 时间。
回答by Kyle
In mathematics, the sieve of Atkin is a fast, modern algorithm for finding all prime numbers up to a specified integer.
在数学中，阿特金筛法是一种快速、现代的算法，用于查找指定整数以内的所有素数。
Wikipedia article(contains pseudocode)
维基百科文章（包含伪代码）
To address doing this recursively, perhaps the Sieve of Eratosthenescan be implemented recursively. This pagemight be helpful, as it appears to discuss a recursive implementation.
为了解决递归地执行此操作，也许可以递归地实现Eratosthenes的筛选。此页面可能会有所帮助，因为它似乎讨论了递归实现。
回答by nathan
What you need is the Sieve of Forever, here's the code for a recursive prime tester, I think it's quite efficient because it only needs to test the prime factors, let me know what you think ;)
你需要的是永远的筛子，这是递归素数测试器的代码，我认为它非常有效，因为它只需要测试素数，让我知道你的想法;)
By the way, I wouldn't try it with anything above a byte, it seems to take a while with anything over 100.
顺便说一句，我不会尝试使用超过 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;
}
回答by Accipitridae
First, if you want to generatelarge primenumbers (as opposed to test integers for primality) then Pocklington's theoremcomes in handy. This Theorem allows a fast primality test for a candidate p if you know enough prime factors of p-1. Hence the following method is possible: Generenerate a few primes, compute a suitable multiple of their product and test using Pocklington's theorem. If you want to find large prime numbers (e.g. for the RSA cryptosystem) then you will have to apply this method recursivelyfor generating the factors of p-1.
首先，如果您想生成大素数（而不是测试素数的整数），那么 Pocklington 定理就派上用场了。如果您知道 p-1 的足够素因数，则该定理允许对候选 p 进行快速素性测试。因此，以下方法是可能的：生成几个素数，计算它们乘积的合适倍数并使用 Pocklington 定理进行测试。如果您想找到大的素数（例如对于 RSA 密码系统），那么您必须递归地应用此方法来生成 p-1 的因子。
The description above lacks quite a few details. But the method has been analyzed in depth. I think this paper was the fastestmethod when if was published, though some time has gone by since then and someone might have improved it.
上面的描述缺少很多细节。但该方法已被深入分析。我认为这篇论文是if 发表时最快的方法，尽管从那时起已经过去了一段时间，可能有人对其进行了改进。
P.Mihailescu. "Fast Generation of Provable Primes using Search in Arithmetic Progressions", Proceedings CRYPTO 94, Lecture Notes in Computer Science vol 939, Springer 1994, pp. 282-293.
P.米哈莱斯库。“使用算术级数搜索快速生成可证明素数”，Proceedings CRYPTO 94，计算机科学讲义第 939 卷，Springer 1994，第 282-293 页。
回答by Prasoon Saurav
Why recursively?
为什么要递归？
Use better prime number generation algorithm like Sieve of Eratosthenes or even better Sieve of Atkin.
使用更好的素数生成算法，如埃拉托色尼筛法或更好的阿特金筛法。
