November 8th, 2012, 03:45 AM

Prime Number Engine (Sieve)
Sorry I have reached a point of desperation. The assignment is to "Write a program that prompts the user for an integer n, then generate and print a list of all the
primes between 2 and n using the Sieve of Eratosthenes". I have a a skeleton but I cannot figure out why I keep getting an error. Any help would be much appreciated.
Code:
n=int(input("n? "))
x=[]
for i in range(2,(n+1)):
x.append(i)
primes=[2]
p=2
while sum(x) != 0:
i=1
while i*p<=n:
x.remove(i*p)
i=i+1
p=x[0]
primes.append(p)
print(primes)
Apologies, I have no idea how to format this correctly. Again, thanks so much.
November 8th, 2012, 08:23 AM

What error are you getting?
When I try, I get an error at x.remove(i*p) when i=2 and p=3 that "x not in list". I'm not familiar with the sieve but you could trap that error with:
Code:
if i*p in x: x.remove(i*p)
November 8th, 2012, 08:24 AM

Scalar multiplication commutes.
Some integers have more than 2 prime factors.
Try this, it is much closer to working and displays its operation.
Code:
n=int(input("n? "))
x=[]
for i in range(2,(n+1)):
x.append(i)
primes=[2]
p=2
while sum(x) != 0:
i=1
while i*p<=n:
if i*p in x:
x.remove(i*p)
print('%d == %d*%d REMOVED'%(i*p,i,p))
else:
print('%d == %d*%d already gone'%(i*p,i,p))
i=i+1
if x:
p=x[0]
primes.append(p)
print(primes)
[code]
Code tags[/code] are essential for python code and Makefiles!
November 8th, 2012, 08:44 AM

The specific problem you are asking about is that you are trying to remove an item from a list which has already been removed in a previous pass. For example 6 is a multiple of both 2 and 3; when you test for multiples of 2, you remove it, then when you test for multiples of 3 you try to remove it again. You need to add a test for the presence of the tested composite number before trying to remove it:
Code:
currentComposite = i * p
if currentComposite in x:
x.remove(currentComposite)
This is only one problem of several that I've found, but you are on the right track, overall.
November 8th, 2012, 12:54 PM

Originally Posted by b49P23TIvg
Scalar multiplication commutes.
Some integers have more than 2 prime factors.
Try this, it is much closer to working and displays its operation.
Code:
n=int(input("n? "))
x=[]
for i in range(2,(n+1)):
x.append(i)
primes=[2]
p=2
while sum(x) != 0:
i=1
while i*p<=n:
if i*p in x:
x.remove(i*p)
print('%d == %d*%d REMOVED'%(i*p,i,p))
else:
print('%d == %d*%d already gone'%(i*p,i,p))
i=i+1
if x:
p=x[0]
primes.append(p)
print(primes)
Fantastic thank you so much. This got me working. I did not even consider that I was pulling out multiples and then reevaluating them.
I have one more conceptual question. For the line p=x[0], why must we put it after the if statement?
Thanks again!!!
November 8th, 2012, 12:55 PM

Originally Posted by rrashkin
What error are you getting?
When I try, I get an error at x.remove(i*p) when i=2 and p=3 that "x not in list". I'm not familiar with the sieve but you could trap that error with:
Code:
if i*p in x: x.remove(i*p)
I greatly appreciate the input. Thank you so much!
November 8th, 2012, 12:57 PM

Originally Posted by ScholRLEA
The specific problem you are asking about is that you are trying to remove an item from a list which has already been removed in a previous pass. For example 6 is a multiple of both 2 and 3; when you test for multiples of 2, you remove it, then when you test for multiples of 3 you try to remove it again. You need to add a test for the presence of the tested composite number before trying to remove it:
Code:
currentComposite = i * p
if currentComposite in x:
x.remove(currentComposite)
This is only one problem of several that I've found, but you are on the right track, overall.
I did not even think about that. Thank you, I appreciate the input. I have to do a better job of visualizing what the program is actually running. Thanks again!
November 8th, 2012, 01:16 PM

Originally Posted by MightyGreek
I have one more conceptual question. For the line p=x[0], why must we put it after the if statement?
Try the program without
if x:
When is a list True?
When is a list False?
[code]
Code tags[/code] are essential for python code and Makefiles!
November 8th, 2012, 02:11 PM

Originally Posted by b49P23TIvg
Try the program without
if x:
When is a list True?
When is a list False?
I'm going to guess if there is nothing in the list and you try to evaluate the expression, you are returned with False? If that is the case, if x: allows us to use the list while it is True but stops, once the list is False. Am I close?
November 8th, 2012, 02:34 PM

You could read about it.
You could try it in the interpreter
not not []
not not [1,2,3]
Last edited by b49P23TIvg; November 8th, 2012 at 02:36 PM.
[code]
Code tags[/code] are essential for python code and Makefiles!
November 8th, 2012, 02:54 PM

Originally Posted by b49P23TIvg
I see, thank you so much for the patience. As you can see, I have some significant gaps. I will definitely work on them, but again, thank you for taking the time to help.