20100227, 21:25  #1 
Jan 2005
Minsk, Belarus
2^{4}×5^{2} Posts 
Thinking of a new project: Sieve of Eratosthenes
Hello people :)
While compiling the tables of the primecounting function and its fluctuations, I realized that it's possible to set up a distributed project to sieve all the primes up to, say, 10^{18}, and maybe further. Tomás Oliveira e Silva used a segmented sieve and reached 1.6*10^{18} within ~400 CPU years. Unfortunately, Tomás recorded the prime counts only every 10^{12}. But these results could be used for doublechecking. I propose to save the prime counts every 10^{9}. For the range of 10^{18} it will take 10^{9} data points. To save the space, we could record the difference pi(x)li(x) multiplied by 2 (to get rid of roundoff errors) and rounded to the nearest integer. It will take just 4 bytes for each such point. Moreover, it seems that the difference between two adjacent points never exceeds 2^{15} by the absolute value, so only 2 last bytes could be stored. There's an example of such a database for the range up to 10^{14}: http://www.primefan.ru/stuff/primes/pi.dat (200 000 bytes) It takes only a few seconds to sieve the subrange of 5*10^{8}, so, having the database, one could quickly compute the value of pi(x) for any x within the range. The database could be hosted on the web. * * * * * * Well, the main idea is to implement the siever which could be used by, for example, BOINC contributors. Maybe it has sense to use CUDA there? The sieving routines should be parallelizable this way, I think... However, my programming skills are too low for this; you may just look over my simple implementation of the classical sieve up to 10^{15}, which takes over 1 minute (!) at 1GHz for the subrange of 10^{9}: http://www.primefan.ru/stuff/soft/siever.txt With best regards, Andrey V. Kulsha 
20100228, 00:24  #2 
Banned
"Luigi"
Aug 2002
Team Italia
2×3×5×7×23 Posts 
Hello Andrey!
You are talking about small primes, that could be proven in milliseconds. A friend of mine wrote an assembly program for MSDOS that calculated prime numbers in the first 2^{32} naturals in 3 seconds on 20 MHz machines. The question is: is it worth it? Who will be in charge to update 10^{18} values into the database? Luigi 
20100228, 00:57  #3 
A Sunny Moo
Aug 2007
USA (GMT5)
6249_{10} Posts 
PrimeGrid did a project sort of like this a while back with their nowdefunct "Primegen" subproject; I'm not sure what method they used or how far they got, though they hit it with enough resources that I wouldn't be surprised if they got much farther 10^{18}.
Edit: I just checked and it seems they stopped at 640,000,000,000, which is somewhere between 2^{32} and 2^{33}. See this thread in their forum for more info. Last fiddled with by mdettweiler on 20100228 at 01:03 
20100228, 01:07  #4 
Jun 2003
3×17×101 Posts 
Nobody's talking about storing primes  only prime counts.

20100228, 01:32  #5 
"Mark"
Apr 2003
Between here and the
14442_{8} Posts 
I'm not understanding the usefullness of this.

20100228, 07:13  #6  
Jan 2005
Minsk, Belarus
190_{16} Posts 
Quote:
Where did you see 10^{18} values? :surprised Last fiddled with by XYYXF on 20100228 at 08:06 

20100228, 10:32  #7 
Dec 2008
179 Posts 
That seems to be an extremely slow way to compute pi(x). Best known methods are much faster, and don't require a huge database.

20100228, 12:12  #8  
"Robert Gerbicz"
Oct 2005
Hungary
2×3^{2}×83 Posts 
Quote:
As far as I know Mathematica is also using precomputed table and sieve to compute pi(x). 

20100228, 13:24  #9 
Jan 2005
Minsk, Belarus
2^{4}·5^{2} Posts 

20100228, 13:59  #10 
"Mark"
Apr 2003
Between here and the
2·3,217 Posts 
So one has a database filled with pi(x) for many values of x. Again, what is the value of that?

20100228, 15:05  #11  
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
2^{2}×11×97 Posts 
http://primes.utm.edu/nthprime/ goes up to 10^12. Do you really need any more? If so, it might be helpful to take some hints on how they did it (look at "Algorithm" on that page).
Quote:
On an Athlon 2400XP with 1.5GB RAM, it took 88 minutes and 41 seconds to search all numbers up to 40 billion (about 10*2^32). Guesstimating a linear scaling, it could probably do up to 2^32 in about 89 minutes. Not bad, but not 3 seconds on a 20 MHz machine. Last fiddled with by MiniGeek on 20100228 at 15:05 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Sieve of Eratosthenes  bhelmes  Number Theory Discussion Group  43  20180313 01:04 
New GPU accelerated sieve of Eratosthenes  cseizert  Programming  8  20161027 05:55 
Sieve of Eratosthenes  Raman  Programming  4  20090119 17:12 
Sieve of Eratosthenes  jchein1  Homework Help  6  20070827 13:51 
Prime in Riesel Sieve Project  Sloth  Prime Sierpinski Project  1  20060510 02:02 