Return to Question

deleted 57 characters in body; edited title

Source Link

edited Sep 11, 2015 at 17:13

34.9k
13
133
237

Python: Sieve of Eratosthenes in Python 3

Currently, the code will generate a range of natural numbers from 1 to N and store it in a list. Then the program will iterate through that list, marking each multiple of a prime as 0 and storing each prime in a secondary list.

This is a translation of a TI-Basic program, shown here, so the same description still applies.

Here's an animation,:

One of the main optimizations that I want to see implemented would be the actual removal of prime multiples from the list instead of simply setting them to 0. As it is currently written, this would be a challenge to perform without adding in another if statement. Any suggestions would be helpful.

Here is the code, any optimizations would be helpful.

def sieve(end):
    prime_list = []
    sieve_list = list(range(end+1))
    for each_number in range(2,end+1):
        if sieve_list[each_number]:
            prime_list.append(each_number)
            for every_multiple_of_the_prime in range(each_number*2, end+1, each_number):
                sieve_list[every_multiple_of_the_prime] = 0
    return prime_list

[Here's a link to PythonTutor][Tutor], which will visualize the code in operation.

[Tutor]: http://www.pythontutor.com/visualize.html#code=def+sieve(end%29%3A%0D%0A++++prime_list+%3D+%5B%5D%0D%0A++++sieve_list+%3D+list(range(end%2B1%29%29%0D%0A++++for+each_number+in+range(2,end%2B1%29%3A%0D%0A++++++++if+sieve_list%5Beach_number%5D%3A%0D%0A++++++++++++prime_list.append(each_number%29%0D%0A++++++++++++for+every_multiple_of_the_prime+in+range(each_number*2,+end%2B1,+each_number%29%3A%0D%0A++++++++++++++++sieve_list%5Bevery_multiple_of_the_prime%5D+%3D+0%0D%0A++++return+prime_list%0D%0A%0D%0A%0D%0Asieve(10%29&mode=display&origin=opt-frontend.js&cumulative=true&heapPrimitives=false&textReferences=false&py=3&rawInputLstJSON=%5B%5D&curInstr=0

Python: Sieve of Eratosthenes

Currently, the code will generate a range of natural numbers from 1 to N and store it in a list. Then the program will iterate through that list, marking each multiple of a prime as 0 and storing each prime in a secondary list.

This is a translation of a TI-Basic program, shown here, so the same description still applies.

Here's an animation,

Here is the code, any optimizations would be helpful.

def sieve(end):
    prime_list = []
    sieve_list = list(range(end+1))
    for each_number in range(2,end+1):
        if sieve_list[each_number]:
            prime_list.append(each_number)
            for every_multiple_of_the_prime in range(each_number*2, end+1, each_number):
                sieve_list[every_multiple_of_the_prime] = 0
    return prime_list

[Here's a link to PythonTutor][Tutor], which will visualize the code in operation.

Sieve of Eratosthenes in Python 3

Currently, the code will generate a range of natural numbers from 1 to N and store it in a list. Then the program will iterate through that list, marking each multiple of a prime as 0 and storing each prime in a secondary list.

This is a translation of a TI-Basic program, shown here, so the same description still applies.

Here's an animation:

def sieve(end):
    prime_list = []
    sieve_list = list(range(end+1))
    for each_number in range(2,end+1):
        if sieve_list[each_number]:
            prime_list.append(each_number)
            for every_multiple_of_the_prime in range(each_number*2, end+1, each_number):
                sieve_list[every_multiple_of_the_prime] = 0
    return prime_list

[Here's a link to PythonTutor][Tutor], which will visualize the code in operation.

Source Link

asked Sep 11, 2015 at 16:49

Slinky

Python: Sieve of Eratosthenes

Currently, the code will generate a range of natural numbers from 1 to N and store it in a list. Then the program will iterate through that list, marking each multiple of a prime as 0 and storing each prime in a secondary list.

This is a translation of a TI-Basic program, shown here, so the same description still applies.

Here's an animation,

Here is the code, any optimizations would be helpful.

def sieve(end):
    prime_list = []
    sieve_list = list(range(end+1))
    for each_number in range(2,end+1):
        if sieve_list[each_number]:
            prime_list.append(each_number)
            for every_multiple_of_the_prime in range(each_number*2, end+1, each_number):
                sieve_list[every_multiple_of_the_prime] = 0
    return prime_list

[Here's a link to PythonTutor][Tutor], which will visualize the code in operation.