Sieve of Eratosthenes in Python

Hello All, I working on a python project and I am confused sieve of eratosthenes coding problem. The problem statement is Given a number n, print all primes smaller than or equal to n. It is also given that n is a small number. I am trying to solve this problem by Efficient Approach

A prime number is a number that is divisible by only two numbers – themselves and 1

Example:
Input: n =10
Output: 2 3 5 7

I have checked sieve of eratosthenes coding problem on google and I have found this problem post. Iam sharing one coding example. Can anyone explain me, how sieve of eratosthenes program works? or explain with another example?

def SieveOfEratosthenes(n):
    prime = [True for i in range(n+1)]
    p = 2
    while (p * p <= n):
        if (prime[p] == True):
 
            # Update all multiples of p
            for i in range(p * p, n+1, p):
                prime[i] = False
        p += 1
 
    # Print all prime numbers
    for p in range(2, n+1):
        if prime[p]:
            print p,

By Aarti yadav via Discussions on Python.org at 07Jul2022 07:34:

Hello All, I working on a python project and I am confused sieve of
eratosthenes coding problem. The problem statement is Given a number n,
print all primes smaller than or equal to n. It is also given that n is
a small number. I am trying to solve this problem by Efficient Approach

A prime number is a number that is divisible by only two numbers – themselves and 1

Example:
Input: n =10
Output: 2 3 5 7

I have checked sieve of eratosthenes coding problem on google and I have found this problem post. Iam sharing one coding example. Can anyone explain me, how sieve of eratosthenes program works? or explain with another example?

Have you first read a description of the algorithm, such as this one?

The code you show is not how I would ever write a the sieve.

What the code you show does is make an array, declare every value in the
array to be prime (or “potentially prime”), then for each “true” entry
in the array:

  • it is prime because no prior value has scrubbed it
  • scrub the “primeness” of all the multiples of the value

Whn I write this algorithm I kind of treat the array of potential primes
virtually: I don’t make it and instead just keep a list of all the
previous primes found so far. Then for each potential prime n I test
it against all the previous primes up to sqrt(n). So I don’t need an
upper limit and don’t need to allocate the initial array; I can just run
a counter n from 3 upwards. And I usually only count the odd values
i.e. count by 2, since all the even numbers are known to not be prime.

I think the 2 approaches might have similar overall runtime costs.

Cheers,
Cameron Simpson cs@cskk.id.au

1 Like

You may be interested in this preprint: https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

tl;dr - there’s a big difference in performance between SoE done right and some other things that claim to be the sieve of Eratosthenes.

2 Likes

The point of the sieve of Eratosthenes algorithm is that you never need to do a division test, you can eliminate values which cannot possibly be prime without needing to test whether or not they are prime.

If you are doing this:

“Then for each potential prime n I test it against all the previous primes up to sqrt(n).”

then you’re not using the sieve of Eratosthenes, you are using some other algorithm (likely a non-naive trial division, or possibly a wheel algorithm).

By the way, once you get past the first two primes 2, 3, you only need to test the number just before, and just after, each multiple of 6. That allows you to skip testing 2 out of 3 potential candidate primes instead of just 1 out of 2 (the even numbers).

(This is not the sieve of Eratosthenes either.)


def primes():

    yield 2

    yield 3

    i = 6

    while True:  # Run forever.

        a = i - 1

        b = i + 1

        if isprime(a): yield a

        if isprime(b): yield b

        i += 6

There are more complex wheel arrangements that can skip even more.

I recommend you read the Wikipedia article you linked to and look carefully at the animation. In my opinion, the animation could be improved, but it gives an idea of the process.

There is a version of Euler’s sieve popular in Haskell circles, where it is often wrongly described a the sieve of Eratosthenes.


primes = sieve [2..]

sieve (p : xs) = p : sieve [x | x <- xs, x `mod` p > 0]

That is delightfully concise, but hugely inefficient. Asymptotic behaviour is worse than trial division.

A Python version might be:


def sieve():

    # Very slow, very inefficient version of Euler's sieve.

    nums = itertools.count(2)

    while True:

        prime = next(nums)

        yield prime

        nums = filter(lambda v, p=prime: (v % p) != 0, nums)

I don’t know if it is possible to write an efficient Euler’s sieve version.

In my own limited testing, the fastest method I found to produce smallish primes was this version of the Croft Spiral.


def croft():

    # Implementation is based on erat3 from here:

    #   http://stackoverflow.com/q/2211990

    # and this website:

    #   http://www.primesdemystified.com/

    # Memory usage increases roughly linearly with the number of primes seen.

    # dict ``roots`` stores an entry p**2:p for every prime p.

    for p in (2, 3, 5):

        yield p

    roots = {9: 3, 25: 5}  # Map d**2 -> d.

    primeroots = frozenset((1, 7, 11, 13, 17, 19, 23, 29))

    selectors = (1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0)

    for q in itertools.compress(

            # Iterate over prime candidates 7, 9, 11, 13, ...

            itertools.islice(itertools.count(7), 0, None, 2),

            # Mask out those that can't possibly be prime.

            itertools.cycle(selectors)

            ):

        # Using dict membership testing instead of pop gives a

        # 5-10% speedup over the first three million primes.

        if q in roots:

            p = roots[q]

            del roots[q]

            x = q + 2*p

            while x in roots or (x % 30) not in primeroots:

                x += 2*p

            roots[x] = p

        else:

            roots[q*q] = q

            yield q

At some point, once you hit truly enormous candidates, it becomes impractical to store all the previously seen primes in order to perform trial division. At that point I guess the only practical method is to swap to a probabilistic method such as Miller-Rabin.

If Tim Peters were around, he would probably argue in favour of just using Miller-Rabin (augmented by a couple of trial division tests on the small primes to weed out obvious composites) for everything. But where’s the fun in that?

By Steven D’Aprano via Discussions on Python.org at 07Jul2022 17:18:

The point of the sieve of Eratosthenes algorithm is that you never need
to do a division test, you can eliminate values which cannot possibly
be prime without needing to test whether or not they are prime.

Ah. I’ve been considering division (or remainder) to be cheap. Which I
guess it is not compared to multiplication or successive addition.

If you are doing this:
“Then for each potential prime n I test it against all the previous
primes up to sqrt(n).”
then you’re not using the sieve of Eratosthenes, you are using some
other algorithm (likely a non-naive trial division, or possibly a wheel
algorithm).

I guess so. I do like not having to have a search array as large as my
upper bound, or indeed having an upper bound at all :slight_smile:

But as you say, two algorithms producing the same answers are still two
distinct algorithms.

By the way, once you get past the first two primes 2, 3, you only need
to test the number just before, and just after, each multiple of
6
. That allows you to skip
testing 2 out of 3 potential candidate primes instead of just 1 out of
2 (the even numbers).

Ah, nice. I used to wonder about 2x3 and tossed it aside as too tricky
instead of trying to do it. Perhaps because then I’d want to do 2x3x5
and then 2x3x5x7 etc.

There are more complex wheel arrangements that can skip even more.

Right.

I recommend you read the Wikipedia article you linked
to
and look
carefully at the animation. In my opinion, the animation could be
improved, but it gives an idea of the process.

I saw the animation. I suspect I was thinking of my test process as
being a trite refactoring of the colour-the-array approach which traded
up front storage and colouring for post-new-prime implied colouring via
the factor tests.

[… more cool stuff snipped …]

Cheers,
Cameron Simpson cs@cskk.id.au

By Cameron Simpson via Discussions on Python.org at 07Jul2022 23:48:

There are more complex wheel arrangements that can skip even more.

Right.

Though I’m disappointed in myself for not realising this while watching
the popular Amazon fantasy series, The Wheel Of Primes.

Thank you, thank you,
Cameron Simpson cs@cskk.id.au