Interview question : What is the fastest way to generate prime number recursively ?
Posted
by
hilal
on Stack Overflow
See other posts from Stack Overflow
or by hilal
Published on 2010-12-29T05:35:46Z
Indexed on
2010/12/29
5:54 UTC
Read the original article
Hit count: 179
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.
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);
}
© Stack Overflow or respective owner