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: 155

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

Related posts about java

Related posts about algorithm