Friday, November 9, 2012

Print prime numbers from 1 to 10 Million

Print all prime numbers from 1 to 10 million.

Approach
Prime number is one which is divisible by 1 and itself. So to find if a number 'X' is prime, we need to divide each and every number with 'X'. However this can be optimized. Instead of checking for all the numbers, check upto square-root of 'X'.
Further to this, Sieve has proposed an optimized solution to calculating primes.
If a number is prime then any multiple of it is not a prime

With this approach, I was able to print all prime numbers from 1 to 10 million, in 4 seconds on my laptop.

Solution

No comments:

Post a Comment

UA-36403895-1