1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Posts
6
Rep Power
0

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.
2. 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)`
3. 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:
i=i+1
if x:
p=x[0]
primes.append(p)
print(primes)```
4. 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.
5. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Posts
6
Rep Power
0
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:
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!!!
6. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Posts
6
Rep Power
0
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!
7. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Posts
6
Rep Power
0
Originally Posted by Schol-R-LEA
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!
8. 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?
9. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Posts
6
Rep Power
0
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?

You could try it in the interpreter

not not []

not not [1,2,3]
Last edited by b49P23TIvg; November 8th, 2012 at 03:36 PM.
11. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Posts
6
Rep Power
0
Originally Posted by b49P23TIvg