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

Wkwkwkw..., cool lemma... + 6 isn't it?

ReplyDeleteSo, it is Timo's Algorithms right? wkwkwkw...

whice one is faster?

ReplyDeletesieve or this one>?

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

ReplyDeleteIt's very awesome ..

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

I like algorithms and practice hard every day.

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

ReplyDeleteno wonder :D

:kiss