Search code examples
pythonpython-3.xprimesenumeratesieve-algorithm

Prime Sieve algorithm in Python : Help Explaining


I came across this prime sieve using the enumerate function which I vaguely understand, I understand the general idea behind the code, i.e. turning all the non-prime values in the list of 'True' to 'False' and then out of that creating a prime list. But I'm not exactly sure how to interpret the code after line 5, is is_prime a function or a variable? I'm slightly confused

def prime_sieve(n):
    sieve = [True] * n #Generates a list of 'True' of length n
    sieve[:2] = [False, False]  #  0 and 1 are not primes
    primes = []
    for prime, is_prime in enumerate(sieve): 
        if not is_prime:
            continue
        primes.append(prime)
        for not_prime in range(prime*prime, n, prime):
            sieve[not_prime] = False 
    return primes, sieve

Solution

  • def prime_sieve(n):
        sieve = [True] * n #Generates a list of 'True' of length n
        sieve[:2] = [False, False]  #  0 and 1 are not primes
        primes = []
    

    Declares the function, sets the variables. Sieve is a list of booleans meant to represent whether the number of a given index is prime or not. Primes is set to an empty list of primes found so far.

        for prime, is_prime in enumerate(sieve): 
    

    Iterate through an enumerated list of all numbers, and their boolean counterparts. Enumerate is like iterating over a list, but also having the index of all list variables. Since enumerate gives two variables for every list element, you need to use two variables to unpack it. 'prime' is going to be a number, the index of the list element being accessed, and 'is_prime' is the boolean value at that index.

            if not is_prime:
                continue
    

    If a number has previously been declared to be 'not prime', then skip it.

    primes.append(prime)
    

    If not, add it to the list of prime numbers already found.

            for not_prime in range(prime*prime, n, prime):
                sieve[not_prime] = False 
    

    Starting at the prime's square to the end, all numbers that are divisible by the prime are set to False

     return primes, sieve
    

    Returns the list of all prime numbers, and the boolean list of all numbers in the sieve.