Interview question : What is the fastest way to generate prime number recursively?

Question

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);
   }

Answer 1

In mathematics, the sieve of Atkin is a fast, modern algorithm for finding all prime numbers up to a specified integer.

Wikipedia article (contains pseudocode)

To address doing this recursively, perhaps the Sieve of Eratosthenes can be implemented recursively. This page might be helpful, as it appears to discuss a recursive implementation.

Answer 2

For recurrsion, You should use memoization to improve your recursive function, means if you finding prime number save it in array, and in call to isPrime(n) first check the number exists in array if not call to isPrime(n, (int) Math.sqrt(n)). also if isPrime(n,i) returns true, add it to prime list, it's better your array be sorted to do binary search, in C# there is sorted list, and binary search operation [making list of n item takes O(n log n) and searching is O(log(n))] i didn't know about java [but you can implement it].

Edit: your current approach is O(n sqrt(n)) but with my approch it can be in same order! but better performance, in fact the order is O(n sqrt(n) / log (n) + n log(n/log(n))) and because log(n) is smaller then n^Epsilon, it's better to say it's O(n sqrt(n)) but as you can see it will run log(n) time faster.

Also it's better do i-2 not i-- and some extra check in startup to run algorithm 2*log(n) time faster.

Answer 3

What you need is the Sieve of Forever, here's the code for a recursive prime tester, I think it's quite efficient because it only needs to test the prime factors, let me know what you think ;)

By the way, I wouldn't try it with anything above a byte, it seems to take a while with anything over 100.

public boolean isPrime(byte testNum)
{
    if ( testNum <= 1 )
        return false;
    for ( byte primeFactor = 2; primeFactor < testNum; primeFactor++ )
        if ( isPrime(primeFactor) )
            if ( testNum % primeFactor == 0 )
                return false;
    return true;
}

Answer 4

First, if you want to generate large prime numbers (as opposed to test integers for primality) then Pocklington's theorem comes in handy. This Theorem allows a fast primality test for a candidate p if you know enough prime factors of p-1. Hence the following method is possible: Generenerate a few primes, compute a suitable multiple of their product and test using Pocklington's theorem. If you want to find large prime numbers (e.g. for the RSA cryptosystem) then you will have to apply this method recursively for generating the factors of p-1.

The description above lacks quite a few details. But the method has been analyzed in depth. I think this paper was the fastest method when if was published, though some time has gone by since then and someone might have improved it.

P.Mihailescu. "Fast Generation of Provable Primes using Search in Arithmetic Progressions", Proceedings CRYPTO 94, Lecture Notes in Computer Science vol 939, Springer 1994, pp. 282-293.

Answer 5

Why recursively?

Use better prime number generation algorithm like Sieve of Eratosthenes or even better Sieve of Atkin.