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