Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
November 8th, 2012, 04:45 AM
 MightyGreek
Registered User

Join Date: Nov 2012
Posts: 6
Time spent in forums: 25 m 5 sec
Reputation 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:
 Original - 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
November 8th, 2012, 09:23 AM
 rrashkin
Contributing User

Join Date: May 2012
Location: 39N 104.28W
Posts: 141
Time spent in forums: 2 Days 42 m 37 sec
Reputation Power: 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
November 8th, 2012, 09:24 AM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,187
Time spent in forums: 1 Month 3 Weeks 2 Days 13 h 13 m 26 sec
Reputation Power: 455
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)```
__________________
[code]Code tags[/code] are essential for python code!

#4
November 8th, 2012, 09:44 AM
 Schol-R-LEA
Commie Mutant Traitor

Join Date: Jun 2004
Location: Norcross, GA (again)
Posts: 1,799
Time spent in forums: 1 Month 2 Weeks 3 Days 2 h 1 m 47 sec
Reputation Power: 1569
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.
__________________
Rev First Speaker Schol-R-LEA;2 JAM LCF ELF KoR KCO BiWM TGIF
#define KINSEY (rand() % 7) λ Scheme is the Red Pill
Scheme in ShortUnderstanding the C/C++ Preprocessor
Taming PythonA Highly Opinionated Review of Programming Languages for the Novice, v1.1

FOR SALE: One ShapeSystem 2300 CMD, extensively modified for human use. Includes s/w for anthro, transgender, sex-appeal enhance, & Gillian Anderson and Jason D. Poit clone forms. Some wear. \$4500 obo. tverres@et.ins.gov

#5
November 8th, 2012, 01:54 PM
 MightyGreek
Registered User

Join Date: Nov 2012
Posts: 6
Time spent in forums: 25 m 5 sec
Reputation Power: 0
Quote:
 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!!!

#6
November 8th, 2012, 01:55 PM
 MightyGreek
Registered User

Join Date: Nov 2012
Posts: 6
Time spent in forums: 25 m 5 sec
Reputation Power: 0
Quote:
 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
November 8th, 2012, 01:57 PM
 MightyGreek
Registered User

Join Date: Nov 2012
Posts: 6
Time spent in forums: 25 m 5 sec
Reputation Power: 0
Quote:
 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
November 8th, 2012, 02:16 PM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,187
Time spent in forums: 1 Month 3 Weeks 2 Days 13 h 13 m 26 sec
Reputation Power: 455
Quote:
 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
November 8th, 2012, 03:11 PM
 MightyGreek
Registered User

Join Date: Nov 2012
Posts: 6
Time spent in forums: 25 m 5 sec
Reputation Power: 0
Quote:
 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?

#10
November 8th, 2012, 03:34 PM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,187
Time spent in forums: 1 Month 3 Weeks 2 Days 13 h 13 m 26 sec
Reputation Power: 455

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
November 8th, 2012, 03:54 PM
 MightyGreek
Registered User

Join Date: Nov 2012
Posts: 6
Time spent in forums: 25 m 5 sec
Reputation Power: 0
Quote:
 Originally Posted by b49P23TIvg You could read about it. You could try it in the interpreter not not [] not not [1,2,3]

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.

 Viewing: Dev Shed Forums > Programming Languages > Python Programming > Prime Number Engine (Sieve)