Tuesday, 6 August 2013

python coding - Sieve of eratosthenes how to draw from list?

python coding - Sieve of eratosthenes how to draw from list?

Hi all I have a question im working on in python and seem to be stuck on
step 3 and 4. Any help would be great. This is the question:
Write a program which implements a function for the sieve of Eratosthenes.
(http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes). The sieve of
Eratosthenes is a simple algorithm for finding all prime numbers up to a
specified integer. It was created by the ancient Greek mathematician
Eratosthenes. The algorithm to find all the prime numbers less than or
equal to a given integer n: a. Create a list of integers from two to n: 2,
3, 4, ..., n b. Start with a counter i set to 2, i.e. the first prime
number c. Starting from i+i, count up by i and remove those numbers from
the list, i.e. 2*i, 3*i, 4*i, aso.. d. Find the first number of the list
following i. This is the next prime number. e. Set i to the number found
in the previous step f. Repeat steps 3 and 4 until i is greater than n. g.
All the numbers, which are still in the list, are prime numbers
This is what I have coded so far just don't know how to get the prime
numbers from the list and remove the others....:
def main():
n = int(input("Please enter the limititing integer that you want to find
all the prime numbers for: "))
num_list = []
num = 1
for i in range(2, n + 1):
num = num + 1
num_list.append(num)
i = 2
for p in range(2, n):
non_prime = num * i
#while non_prime < n:
if non_prime == num:
num_list.remove(num)
i = i + 1
print(num_list)
main() # Call the main function
Thank for your help im banging my head against the wall as we speak.

No comments:

Post a Comment