java面试问题:递归生成素数的最快方法是什么?
素数的生成很简单,但找到它并递归生成(素数)的最快方法是什么
这是我的解决方案。然而,这并不是最好的方法。我认为是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) 个答案