Python Forum
sieve of eratosthenes implementation
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
sieve of eratosthenes implementation
#1
Can anyone provide me a simple implementation of sieve of eratosthenes algorithm ? I'm finding it hard to understand
Reply
#2
You can read wikipedia: Sieve of Eratosthenes.

In simple terms it is eliminating numbers which are not primes. Remaining numbers are primes.

Some dummy quick-and-dirty example to give general idea (skipped part where you actually find whether number is prime, provided in tuple):

- get numbers which are not primes
- get gaps between non-prime numbers (primes)

import heapq

def not_prime(max_value, stream=heapq.merge):
    """Yield non-primes under 100."""
    primes = (2, 3, 5, 7)    
    last = object()
    
    non_primes = (range(prime*2, max_value + 1, prime) for prime in primes)
    
    for el in stream(*non_primes):    # to eliminate duplicates
        if el != last:
            last = el
            yield el


def retrive_gaps(non_primes):
    "Yield gaps in non-prime numbers."
    last = 2
    yield last
    for x in non_primes:
        if x != last + 1:
            yield x - 1
        last = x
Practical usage is combining these two functions:

list(gap for gap in retrive_gaps(not_prime(100)))
I'm not 'in'-sane. Indeed, I am so far 'out' of sane that you appear a tiny blip on the distant coast of sanity. Bucky Katt, Get Fuzzy

Da Bishop: There's a dead bishop on the landing. I don't know who keeps bringing them in here. ....but society is to blame.
Reply
#3
In Python wiki (under '20 lines: Prime numbers sieve w/fancy generators') there is much better example of implementation:

import itertools


def iter_primes():
     # An iterator of all numbers between 2 and
     # +infinity
     numbers = itertools.count(2)

     # Generate primes forever
     while True:
         # Get the first number from the iterator
         # (always a prime)
         prime = next(numbers)
         yield prime

         # This code iteratively builds up a chain
         # of filters...
         numbers = filter(prime.__rmod__, numbers)

for p in iter_primes():
    if p > 1000:
        break
    print(p)
I'm not 'in'-sane. Indeed, I am so far 'out' of sane that you appear a tiny blip on the distant coast of sanity. Bucky Katt, Get Fuzzy

Da Bishop: There's a dead bishop on the landing. I don't know who keeps bringing them in here. ....but society is to blame.
Reply
#4
Neither of those is the sieve of eratosthenes. While they both find prime numbers, this post asked a about a very specific method.
In the sieve of Eratosthenes you write all the number from 1 to a max value in a list.
Then starting with 2, you go through the list and eliminate all numbers divisible by that number. The next remaining number in the list (3) is used the same way. and so on until you reach the end of the list. When you reach the end of the list the only remaining number are primes.

Here is a very short implementation that is actually the sieve of Eratosthenes:
# The largest number in the sequence
max_value = 100

# Make sequence fro 1 to max_value
sequence = list(range(1, max_value + 1))

# Start at index 1 which has a value of 2
index = 1

# Check all values in sequence
while index < len(sequence):
    # Include any value that not the starting value or divisible by the starting value
    # In other words eliminate all values divisible by the starting value
    sequence = [number for number in sequence if number % sequence[index] != 0 or
                                                 number == sequence[index]]
    index += 1 # Move on to the next value

print(sequence)
Output:
[1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
Reply
#5
(Dec-20-2019, 08:29 PM)Clunk_Head Wrote: Neither of those is the sieve of eratosthenes. While they both find prime numbers, this post asked a about a very specific method.

I disagree with this assessment. OP asked: "Can anyone provide me a simple implementation of sieve of eratosthenes algorithm"

One should clarify what is algorithm and what is implementation.

Quote:Sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime number, 2. The multiples of a given prime are generated as a sequence of numbers starting from that prime, with constant difference between them that is equal to that prime.[1] This is the sieve's key distinction from using trial division to sequentially test each candidate number for divisibility by each prime.


This algorithm is about eliminating multiples of each prime (non-prime) and from that follows that remaining numbers are primes.

How its done is 'implementation detail'. It doesn't matter if 'marking' is done by creating full list in advance or filtered out on the go. As long it's uses multiples of primes it's implementation of Sieve of Eratostehenes algorithm.
I'm not 'in'-sane. Indeed, I am so far 'out' of sane that you appear a tiny blip on the distant coast of sanity. Bucky Katt, Get Fuzzy

Da Bishop: There's a dead bishop on the landing. I don't know who keeps bringing them in here. ....but society is to blame.
Reply
#6
Quote:It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime number,

You are not doing that, instead your filter comparing each current number to all past numbers. Essentially it's backwards. Also, your first example starts with a list of primes which is not at all part of the original design.

While both generate primes by use of filtering, neither is actually an example of the sieve of eratosthenes.

It's good work, excellent in fact, just not the right work for the question. OP asked for an example that explained how the sieve of eratosthenes worked. Neither of your examples does that. Instead you presented optimized code which is difficult a novice such as OP to understand. If OP had asked how do I generate prime numbers efficiently then your answers would have been suitable.
Reply
#7
If iteratively is concern then from Python wiki code I read comment:

# This code iteratively builds up a chain
# of filters...

I actually don't see big difference between code in wiki and yours. Wiki one takes advantage of generators and don't build intermediate lists. Both use filters as this code is filter by any means:

[number for number in sequence if number % sequence[index] != 0 or number == sequence[index]]
I'm not 'in'-sane. Indeed, I am so far 'out' of sane that you appear a tiny blip on the distant coast of sanity. Bucky Katt, Get Fuzzy

Da Bishop: There's a dead bishop on the landing. I don't know who keeps bringing them in here. ....but society is to blame.
Reply
#8
(Dec-23-2019, 06:50 AM)perfringo Wrote: I actually don't see big difference between code in wiki and yours. Wiki one takes advantage of generators and don't build intermediate lists. Both use filters as this code is filter by any means:

The difference is that your code does not answer the request of OP, which is a problem that a lot of people have. The user asked a simple question. Please provide code that explains the sieve of Eratosthenes, and here you come and show them something that an admitted novice such as OP would have no chance of understanding and doesn't fit the nature of the original exercise which far predates computers.

If you wanted to show them the actual answer and then show them a better way to do it that would also be suitable but you ignored the original request and took the opportunity to show off your brainpan. This forum is about helping people understand and answer their questions. You didn't do that. You are so focused on your code that you refuse to see that. This happens in the homework forum all too often as well. Users tell OPs that the way they are doing things is wrong but that's the way that their teacher wants it done. Yes you can use a dictionary to do stuff easier, but they haven't been taught them yet. Yes list comprehension would look better but they are still on loops. If you want to help consider who you are helping, it's not that tough.

Now I stand by my assertion that you failed OP with your responses and that your code while it produces primes in not actually a proper representation of the sieve of Eratosthenes, and I'm finished with this semantic argument. You reply how you like but in the future when others search this forum for the sieve of Eratosthenes, I can tell you conclusively that they will understand my answer.
Reply
#9
"The beginning of wisdom is the definition of terms." --Socrates

I feel that we argue about different subjects. My point is that these codes are implementation of algorithm (as it not uses trial division).

No argument about whether your code is much simpler and easier to understand. Yes, it is better suited for explanation. I can only plea that OP did not posted it under 'Homework' but in 'General coding help'.

For mimicking paper-and-pencil sieve following approach can be used (uses numpy so not for total beginners, but code itself is very simple):

import numpy as np

def primes(max_value):
    sieve = np.ones(max_value + 1, dtype=np.bool)    # create array of ones/True-s for all values in range, starting from 0
    sieve[:2] = False                                # mark 0 and 1 as False
    for i in range(2, int(max_value**0.5)+1):        # for range 2 to square root of max_value + 1 
        if sieve[i]:                                 # if value on index is True
            sieve[i*i::i] = False                    # mark values False starting from square of value with step of value

    primes = np.nonzero(sieve)[0]                    # primes are all non-zero/non-False (True) values; get True indices
    return primes
Some explanations:

- 'sieve' is representing sieve where initially all 'numbers' are 'True' (primes). 'Numbers' here are actually their indices; True and False representing whether they are marked as primes or non-primes.
- Python uses zero-based indices so we set two first values at indices 0 and 1 to False (non-prime)
- we loop in range of 2 to max value of possible divisor (square root of max_value + 1)
- first iteration with value 2 marks all even values False (non-prime)
- all numbers marked as non-primes starting from square of the number with the step of the number (evens were marked as non-primes in first iteration, so no need to start from multiple of two)
- we get 'sieve' where primes are True and non-primes are 'False'
- we take indices of primes/True values and return them

There is sieve on numbers, non-primes are marked but kept. Only non-marked i.e primes are taken 'out'.

This is pretty fast compared to standard Python loops. Finding primes with max_value of 1_000_000 is practically instant (78_498 primes) with max_value 1_000_000_000 on my machine it took around 10 seconds (50_847_534 primes).
I'm not 'in'-sane. Indeed, I am so far 'out' of sane that you appear a tiny blip on the distant coast of sanity. Bucky Katt, Get Fuzzy

Da Bishop: There's a dead bishop on the landing. I don't know who keeps bringing them in here. ....but society is to blame.
Reply
#10
Basically, given a number n, print all primes smaller than or equal to n. It is also given that n is a small number.

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
Explanation: Only 4 prime numbers are there which are less than or equal to 10

The sieve of Eratosthenes is one of the most efficient ways to find all primes smaller than n when n is smaller than 10 million or so. Following is the algorithm to find all the prime numbers less than or equal to a given integer n by the Eratosthenes method:
Ref - https://www.interviewbit.com/blog/sieve-...tosthenes/

When the algorithm terminates, all the numbers in the list that are not marked are prime.

Firstly write all the numbers from 2,3,4…. n
Now take the first prime number and mark all its multiples as visited.
Now when you move forward take another number that is unvisited yet and then follow the same step-2 with that number.
All numbers in the list left unmarked when the algorithm ends are referred to as prime numbers.
Reply


Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020