## 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).

* 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.

* 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."); } } ```

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

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

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

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 ...

5. I like algorithms and practice hard every day.

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

no wonder :D
:kiss