java - java面试问题:递归生成素数的最快方法是什么?

  显示原文与译文双语对照的内容
110 1

素数的生成很简单,但是找到它并以递归方式生成( 质数)的最快方法是什么?

这是我的解决方案但这不是最好的方法。我想是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);
 }
时间:原作者:0个回答

127 3

在数学中,Atkin筛选器是一种快速。现代的算法,用于查找指定整数的所有素数。

维基百科文章 ( 包含伪代码)

可以递归地实现Eratosthenes的筛选器,以递归处理这个问题。这个页面插件可能很有用,因为它似乎讨论了递归实现。

原作者:
...