Re: The computational complexity of the Sieve of Eratosthenes

On Apr 30, 12:05 pm, user923005 <dcor...@xxxxxxxxx> wrote:
On Apr 30, 3:51 am, Juha Nieminen <nos...@xxxxxxxxxxxxxx> wrote:





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;

}- Hide quoted text -

- Show quoted text -

Using Daniel Bernstein's Primespeed.exe, which is an Aitken sieve
(tail end of the output):

198996103 primes up to 4200000000.
Timings are in ticks. Nanoseconds per tick: approximately 1.000000.
Overall seconds: approximately 5.312000.
Tick counts may be underestimates on systems without hardware tick
support.

Hardware is 2.2 GHz AMD Athlon
Compiler was Microsoft Visual C++, PGO build with the following flags:
/Ox /Ob2 /Oi /Ot /Oy /GT /GL /D "WIN32" /D "NDEBUG" /D "_CONSOLE" /D
"_UNICODE" /D "UNICODE" /FD /MD /Zp16 /arch:SSE /fp:fast /Fo"Release\
\" /Fd"Release\vc80.pdb" /W4 /nologo /c /Wp64 /Zi /Gd /TP /
errorReport:prompt

ecprime by Kim Walisch seems to be even faster:

C:\sieve\ecprime\Release>ecprime.exe 4200000000

100%
primes: 198996103
time: 2.188 sec
.

Relevant Pages

  • Re: The computational complexity of the Sieve of Eratosthenes
    ... primes then it's probably much faster. ... faster than the sieve of Eratosthenes for example in this case: ...     prime.set; ... Nanoseconds per tick: approximately 1.000000. ...
    (comp.programming)
  • Re: Ultimate Prime Sieve -- Sieve Of Zakiya (SoZ)
    ... Sieve of Zakiiya " in which I show and explain the development of ...   I used ... Python version of this in my paper. ... version below is the minimum array size version, ...
    (comp.programming)
  • Re: Sieve of Zakiya
    ... with included benchmarks against the Sieve of Atkin and Sieve of ...   def initialize ... All my SoZ generators have the same form, ... for any prime generator from P3 thru P11. ...
    (comp.lang.ruby)
  • Re: Help needed on separating ethanol from gasoline
    ... doesn't come after me for suggesting this, ... 4A sieve will remove EtOH but no hydrocarbon larger than C3. ... non corrisponde ad un utente   |message is not related to a real ...
    (sci.chem)
  • Re: As the Crow flies.
    ... Almost any sieve would do. ... particular reason (32 bit ints would work just as well). ... real    0m0.090s ...
    (talk.origins)