Friday, January 9, 2009

Generate Prime Numbers With "Dynamic Programming"

Here I present one technique to generate the first N prime numbers with dynamic programming. Dynamic Programming is a paradigm for designing algorithms where the next solution was taken from previous solution.

The memory complexity is O(N).
The time complexity is O(N*C), where C is the number of prime between 2 and sqrt(N) (inclusive).

Advantages:
* flexibility (generate first N prime numbers).
* can check prime until N^2 with complexity O(C).
* in my computer can generate first 200,000 prime numbers below 1 secs.

Disadvantages:
* slow when N is too large.




 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class PrimeDP {

 int primes[];
 public boolean isPrime(int x) {
  if(x<2) return false;
  for(int k=0;k < primes.length && primes[k]*primes[k] <= x;k++)
   if(x%primes[k]==0) return false;
  return true;
 }

 public int getPrime(int index) {
  return primes[index];
 }

 public PrimeDP(int n) {
  primes = new int[n];
  primes[0] = 2;
  primes[1] = 3;
  for(int k=2,i=6;k < n;i+=6) {
   if(isPrime(i-1)) primes[k++]=i-1;
   if(k < n && isPrime(i+1))
   primes[k++]=i+1;
  }
 }

 public static void main(String []args) {
  long a = System.currentTimeMillis();
  int n = 200000;
  PrimeDP p = new PrimeDP(n);
  long b = System.currentTimeMillis();

  System.out.println("time = " + (b-a) + " ms.");
 }
}

6 comments:

  1. Wkwkwkw..., cool lemma... + 6 isn't it?
    So, it is Timo's Algorithms right? wkwkwkw...

    ReplyDelete
  2. whice one is faster?
    sieve or this one>?

    ReplyDelete
  3. Sieve is more faster when N is very large, but Sieve consume more memory.

    ReplyDelete
  4. It's very awesome ..
    How could you get the idea of that algorithm?
    Most of people will think simply way, like
    - initialize 2 first prime numbers, 2 and 3
    - loop from 5 until n with 2 iteration
    - check one by if current iteration is a prime
    - add it to current array, if it is a prime

    You must be very experience in algorithm ...

    ReplyDelete
  5. I like algorithms and practice hard every day.

    ReplyDelete
  6. "I like algorithms and practice hard every day."

    no wonder :D
    :kiss

    ReplyDelete