Interview question : What is the fastest way to generate prime number recursively ?
- by hilal
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);
}
