Sunday, January 20, 2013

Prime Numbers Up to a range K

In order to find all of the prime numbers up to a range  K, we can use Sieve of  Eratosthene.Please find below the algorithm:-


isPrime[0] = false
isPrime[1] = false
for i = 2 to K do
    isPrime[i] = true
for i = 2 to sqrt(K) do
    if isPrime[i] then
        for j = i * i to K with step i do
            isPrime[j] = false
where you can consider isPrime as array of bool up to K. 
I find out about this interesting algorithm during a programming contest and it can be useful for fast calculation of all prime numbers up to a particular range.
For further reading , please refer to below link:
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes