Implementation of Wikipedia's pseudocode of Sieve of Eratosthenes' algorithm

Question

Trying to implement Wikipedia's pseudocode version of Sieve of Eratosthenes' prime number algorithm.

Pseudo code:

algorithm Sieve of Eratosthenes is
    input: an integer  > 1.
    output: all prime numbers from 2 through .

    let  be an array of Boolean values, indexed by integers 2 to ,
    initially all set to true.
    
    for  = 2, 3, 4, ..., not exceeding √ do
        if [] is true
            for  = ², ²+, ²+2, ²+3, ..., not exceeding  do
                set [] := false

    return all  such that [] is true.

My code:

def createListOfPrimes():
  n = int(input("Enter an integer n>1:  "))
  in_list = [True]*(n+1)
  for i in range(2, int(math.sqrt(n)+1)):
    if in_list[i] == True:
      for j in range(i**2, n+1, i):
        in_list[j] == False    
    print(i)

Can someone explain why the function prints wrong values, e.g. for n = 90 createListOfPrimes() prints integers from 2 to 9 inclusively. Been scratching my head over why it's not working - tried various indenting structures with no luck.

EDIT: Implemented @trincot's advise, seems to work. Any suggestions on code improvement are welcomed!

def createListOfPrimes():
  n = int(input("Enter an integer n>1:  "))
  in_list = [True]*(n+1)
  prime_list = []
  for i in range(2, int(math.sqrt(n)+1)):
    if in_list[i] == True:
      for j in range(i**2, n+1, i):
        in_list[j] = False    
  for i in range(2,n+1):
    if in_list[i]==True:
      prime_list.append(i)
  return prime_list

Why are you printing individual numbers at all? The algorithm does no such thing. — Scott Hunter, Jun 17 '22 at 13:12

trincot · Answer 1 · 2022-06-17T13:21:31.320

You didn't implement it as given on Wikipedia.

You have not assigned False, but compared with False. Should be a single =
The print happens in every iteration of the outer loop. This is wrong in two ways:
- It should only print when the list value is True
- It should do this in a separate loop, as the current outer loop only goes up to the square root of n, while you need to check the whole list.

If you make those corrections, it will be aligned to the depicted algorithm. Correct implementations in Python can be found elsewhere on this site, like here.

blunova · Answer 2 · 2022-06-17T13:21:45.950

0

import math

def createListOfPrimes():
    n = int(input("Enter an integer n>1:  "))
    in_list = [True for i in range(n+1)]
    
    for i in range(2, int(math.sqrt(n)+1)):
        if in_list[i] == True:
            for j in range(i**2, n+1, i):
                in_list[j] = False    
        
    return in_list
                
primes = createListOfPrimes()

The == False is wrong and it does not make any sense to call the print function, just return a list. Moreover, you can write the code a lot better, for instance, use a list comprehension for the boolean list.

edited Jun 17 '22 at 13:21

answered Jun 17 '22 at 13:15

blunova

2,122
3
9
21

Please explain. – Scott Hunter Jun 17 '22 at 13:16

score 0 · Answer 3 · answered Jun 17 '22 at 13:18

change in_list[j] == False to in_list[j] = False

import math

def createListOfPrimes():
    n = int(input("Enter an integer n>1:  "))
    in_list = [True]*(n+1)
    for i in range(2, int(math.sqrt(n)+1)):
        if in_list[i] == True:
            for j in range(i**2, n+1, i):
                in_list[j] = False  
    for i, is_prime in enumerate(in_list):
        if is_prime:
            print(i)

createListOfPrimes()

Implementation of Wikipedia's pseudocode of Sieve of Eratosthenes' algorithm

3 Answers3