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