how to find all prime numbers between 1 and 10^9 , i know we can use Sieve_of_Eratosthenes for smaller range, but what when range is too large equivalent to 10^6 ?
Asked
Active
Viewed 838 times
-3
-
close question but for C++ but algorthms are the same: http://stackoverflow.com/questions/453793/which-is-the-fastest-algorithm-to-find-prime-numbers – Benjamin Trent Jul 04 '14 at 21:51
-
110^9 is 0.93 GB if you use 1 byte per value, or ~110MB if you use 1 bit per value. Easily done for modern computers. Why do you say "too larger equivalent to 10^6"? Since 10^9 is not too large for modern computers, I'm voting to close as unclear as to what you're asking – Lasse V. Karlsen Jul 04 '14 at 21:55
-
possible duplicate of [Largest prime factor of a number](http://stackoverflow.com/questions/23287/largest-prime-factor-of-a-number) – Will Jul 04 '14 at 22:12
-
For [Sieve of Erastosthenes](http://en.wikipedia.org/wiki/Sieve_of_Erastosthenes), you can use a *window*. Instead of 2, the bottom of your sieve is an arbitrary positive integer. You also do not progress through the numbers below the sieve using normal iteration, but use integer division or modulus to find the first integer in the sieve (or more typically, the highest integer below the sieve), and only iterate while within the sieve. If sieve fits in CPU cache, using multiple such windows often ends up being faster than a single large window. – Nominal Animal Jul 04 '14 at 23:33
1 Answers
1
Up to 10^9 is not really a big deal. First, only look at odd numbers (because there is only one even prime). Second, use a bit array, so you only need 500 million bits or about 62 Megabyte. Even straightforward code should do that in a few seconds at most.
If you go further, you'd do a sieve for numbers from 1 to 10^9, then from 10^9 + 1 to 2 * 10^9 and so on. Above 10^13 it gets interesting and you need to put a bit more effort into it.
gnasher729
- 51,477
- 5
- 75
- 98