Re: The computational complexity of the Sieve of Eratosthenes

user923005 wrote:
Anyway, there are much better sieves now like the Sieve of Aitken.

Better in which sense? Maybe if you are calculating the first 10^20
primes then it's probably much faster.

It would be interesting, however, to see if the sieve of Atkin is
faster than the sieve of Eratosthenes for example in this case (C++):

namespace
{
const unsigned MAX_VALUE = 4200000000U;
std::bitset<MAX_VALUE/2> prime;

void init()
{
prime.set();
for(unsigned n = 3; n*n < MAX_VALUE; n += 2)
if(prime.test(n/2))
for(unsigned index = n*n; index < MAX_VALUE; index += n*2)
prime.reset(index/2);
}

bool isPrime(unsigned n)
{
if(n <= 1) return false;
return prime.test(n/2);
}
}

The init() function implements the sieve of Eratosthenes. In my
computer (3.4GHz Pentium4) using gcc 4.1.2 (using the compiler options
-O3 -march=pentium4), the init() function takes 1 minute and 12 seconds.
Certainly not the fastest possible way of initializing that bitset
properly, but I would be curious to see if the sieve of Atkin would
perform better.

Here's the rest of the program if you want to test:

namespace
{
unsigned getNthPrime(unsigned n)
{
if(n < 2) return 2;
unsigned count = 1, value = 1;
while(count < n)
{
value += 2;
if(prime.test(value/2))
++count;
}
return value;
}
}

#include <iostream>

int main()
{
init();

std::cout << "There are " << prime.count() << " primes smaller than "
<< MAX_VALUE
<< "\nThe 1000000th prime is " << getNthPrime(1000000)
<< std::endl;
}
.

Relevant Pages

  • Re: Apology to Roedy
    ... implement the Sieve of Eratosthenes as per the question. ... In the real world rarely are you handed a tidy specification to ... gradually glue the bits together or add the complications. ...
    (comp.lang.java.help)
  • Re: simple algorithm for finding primes
    ... Then the numbers that are left are the primes. ... here's a nice little Sieve of Eratosthenes for you: ... enum QPT_result quickPrimeTest (unsigned int l) { ...
    (comp.lang.c)
  • Re: Sieve of Eratosthenes
    ... > i have to program the sieve of eratosthenes in php as a homework. ... > php script which doesn't work properly - actually it doesn't work at ... > the mistake lies somewhere else too. ...
    (comp.lang.php)
  • Re: Segfault City
    ... "\n This program uses Eratosthenes' Sieve to work\n", ... " out all the primes between two limits. ...
    (comp.lang.c)
  • Apology to Roedy
    ... With respect to my latest postings, I have realized that I did not, in ... implement the Sieve of Eratosthenes as per the question. ... Warrick Brown and Gil Grissom ...
    (comp.lang.java.help)