0

Here is the Sieve of Eratosthenes algorithm to find a list of all prime numbers up to a limit N: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

The algorithm makes sense to me. I can understand how and why it works. But I have problem with its time complexity. By wiki:

The bit complexity of the algorithm is O(n (log n) (log log n)) bit operations with a memory requirement of O(n).[15]

However, it contrasts with my intuition that the time complexity of this algorithm should be O(n). I say so because if we see it from the aggregate aspect:

At the beginning, every number in the sequence [2:N] is assumed to be prime. At the end of the algorithm, each element of the sequence will be visited exactly once, to determine whether it is really prime or multiple of another prime number. Each visit takes constant time. So the final T(n) = O(n). But this is not what wiki said. I would like to know what part of my analysis go wrong.

  • 2
    The problem with your reasoning is that you visit non-primes multiple times. – Joseph Wood Jun 15 '18 at 00:56
  • 2
    E.g. For `N = 100`, you mark 84 as "not-prime" 3 times. Once for `p = 2, 3, 7`. – Joseph Wood Jun 15 '18 at 00:57
  • Then is there a way to modify the traditional Sieve of Eratosthenes to make it O(n)? –  Jun 15 '18 at 01:17
  • 1
    I would say no.... The beauty of SoE isn't asymptotic algorithmic complexity but rather its efficiency in generating primes up to a reasonable number. You may think that I just contradicted myself, but remember big-O is concerned with what happens asymptotically. In fact, the current fastest algorithm for generating primes is a version of the SoE by Kim Walisch. I suggest looking at the source code found [here](https://github.com/kimwalisch/primesieve). – Joseph Wood Jun 15 '18 at 01:25
  • I would also check out the answers to this question [Sieve of Atkin](https://stackoverflow.com/q/19388106/4408538), especially the ones (yes, he has multiple answers) by @GordonBGood. – Joseph Wood Jun 15 '18 at 01:30

0 Answers0