CODEWITHSUNDEEP
c++algorithmprimes
Ankur
Ankur

Reputation: 91

Comparison of Sieve of Sundaram and Sieve of Atkin for generating a list of prime numbers

The running time of "sieve of sundaram" for generating a list of prime numbers upto a number n is given O(n*log(n)), according to the link: http://en.wikipedia.org/wiki/Sieve_of_Sundaram. Is this algorithm better than "Sieve of Atkin" and if it is then elaborate a little about how exactly it works?

Upvotes: 3

Views: 7154

Answers (2)

Charles
Charles

Reputation: 11489

In theory:

  • The sieve of Sundaram has an arithmetic complexity O(n log n).
  • The basic sieve of Eratosthenes has arithmetic complexity O(n log log n).
  • Optimized variants of the sieve of Eratosthenes have arithmetic complexity O(n).
  • The sieve of Atkin has not only arithmetic but also bit complexity O(n/log log n).
  • A magical sieve where you are given the primes, in order, takes time O(n/log n).

In practice, the sieve of Sundaram is so slow that no one uses it, and the sieve of Atkin is slower than optimized Eratosthenes variants (although it's at least competitive). Perhaps one day Atkin or something else will displace Eratosthenes but it's not likely to happen soon. (Also, there's no such thing as magic.)

Upvotes: 9

CanSpice
CanSpice

Reputation: 35818

Well, the Wikipedia page for the Sieve of Atkin says:

This sieve computes primes up to N using O(N/log log N) operations

This is better than the Sieve of Sundaram, which is Θ(N log N) in operations (note that this is not O(N log N) -- there's a subtle difference between O() and Θ()).

Upvotes: 2

Related Questions