6

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);
   }
5
  • You're testing for primality, not generating primes. – Matthew Flaschen Dec 29 '10 at 5:40
  • 1
    you can use sieve of Eratosthenes if you want to generate prime numbers up to n. – algo-geeks Dec 29 '10 at 11:31
  • not sure if your interviewer wants best asomtotic time, or just best time, but you can get a local optimization by not sending even numbers into function at all. Just check that 200 is even, subtract one and then each time call generatePrimes(n-=2). – kralco626 Dec 29 '10 at 12:05
  • but that really doesnt buy you much since your checking to see if it's even in the isPrime method anyhow... but i'm just saying... you can do some contant time work, and cut your calls to the generatePrimes function in half. – kralco626 Dec 29 '10 at 12:06
  • This seems like a really stupid interview question. – Nick Johnson Sep 29 '11 at 1:13
3

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.

21
  • There is no way to generate primes < n in O(n). Memoization does not help here. What you're describing is a good optimization, but it's not memoization and it's not O(n), it's still O(n*sqrt(n)) because primality testing will still be O(sqrt n). – IVlad Dec 29 '10 at 11:04
  • @lVald, In fact my approach is O(n) in average, (like Qsort is n log n) because there is a finite number of call to IsPrime(n,i) I think it's constant factor (really no it's not constant but for example log log log log n is constant in current PCs), and memoization used widly because the approach is isPrime(n, i - 2) so with hi probability number is checked unless is prime (1/log n) – Saeed Amiri Dec 29 '10 at 11:10
  • @lVald, I'll edit my answer to say more exact time. – Saeed Amiri Dec 29 '10 at 11:16
  • IVlad returns :) so there will be answer in 10 minutes :) – user467871 Dec 29 '10 at 11:33
  • @Saeed - I am really not sure what you're describing. Can you post pseudocode? I don't see where sqrt(n) * log(n) comes from. @hilal - you already have a good answer given by @Kyle S. Look up the sieve of Eratosthenes on google. If you managed to translate the classical algorithm into a recursive implementation you'll have no problem doing it for the sieve. The sieve runs in O(n log log n). – IVlad Dec 29 '10 at 11:42
4

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.

5
  • 1
    but in the question it is mentioned that : to find it and generate( prime numbers) it recursively – user467871 Dec 29 '10 at 5:46
  • Perhaps my edit addresses the recursive requirement; I'm not sure. – Kyle Dec 29 '10 at 6:14
  • I just edited it again to include a link to a page at CMU's site that might be helpful. – Kyle Dec 29 '10 at 6:23
  • +1 for the interesting CMU link, -1 for suggesting sieve of Atkin (sorry :) ) - its theoretical complexity might be better but it's very hard to implement right (the pseudocode in WP article is bogus and it says so on its talk page) and those that tried are saying (here, on SO) that the constant factors involved make it still slower that properly wheel-erized Sieve of Eratosthenes, for 32-bit range of numbers for sure. – Will Ness Oct 16 '14 at 20:13
  • @WillNess: Agreed. I'm not aware of any range of numbers on which the Atkin-Bernstein sieve outperforms a suitably-optimized SoE in practice. primegen performs very poorly beyond $2^{32}$, and I don't know of any other serious implementations. (Google finds plenty of toy implementations.) – Charles Feb 16 '15 at 21:21
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;
}
4
  • 2? -- 3?2? -- 4?2? -- 5?2?3?2?4?2? -- 6?2? -- 7?2?3?2?4?2?5?2?3?2?4?2?6?2? -- 8?2? -- 9?2?3?2? -- 10?2? -- 11?2?3?2?4?2?5?2?3?2?4?2?6?2?7?2?3?2?4?2?5?2?3?2?4?2?6?2?8?2?9?2?3?2?10?2? -- ... this is hardly fast, let alone fastest. :) – Will Ness Feb 15 '14 at 18:41
  • so no, it is not efficient at all. it is extremely inefficient. you make gi-nor-mous amounts of work to spare one measly meager remainder test. this well might be the most inefficient impl I ever saw, ever. :) – Will Ness Feb 15 '14 at 18:53
  • 2
    This is magnificently slow, and I love it. ECPP and AKS are polylogarithmic, trial division is polynomial, and this is exponential. Where else can you see gaps like that? – Charles Feb 16 '15 at 21:57
  • so, it's isPrime n = n > 1 && []==[f | f <- [2..n-1], isPrime f && rem n f == 0]. (and the call to isPrime f is entirely superfluous, of course). still the champion in slowness. – Will Ness Aug 20 '16 at 15:27
1

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.

0

Why recursively?

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

1
  • in the question it is mentioned that : to find it and generate( prime numbers) it recursively – user467871 Dec 29 '10 at 5:49