Prime Number Engine (Sieve)

Dev Shed Forums Sponsor:

November 8th, 2012, 03: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 ip<=n: x.remove(ip) i=i+1 p=x[0] primes.append(p) print(primes)

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

rrashkin

Contributing User

Join Date: May 2012

Location: 39N 104.28W

Posts: 90

Time spent in forums: 1 Day 13 h 37 m 44 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)

November 8th, 2012, 08:24 AM

b49P23TIvg

Contributing User

Join Date: Aug 2011

Posts: 3,350

Time spent in forums: 1 Month 2 Weeks 3 Days 7 h 38 m 45 sec
Reputation Power: 383

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!

November 8th, 2012, 08:44 AM

Schol-R-LEA

Commie Mutant Traitor

Dev Shed Intermediate (1500 - 1999 posts)

Join Date: Jun 2004

Location: Norcross, GA (again)

Posts: 1,759

Time spent in forums: 1 Month 2 Weeks 2 Days 3 h 38 m 3 sec
Reputation Power: 1568

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 Short • Understanding the C/C++ Preprocessor
Taming Python • A 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

November 8th, 2012, 12: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!!!

November 8th, 2012, 12: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!

November 8th, 2012, 12: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

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

b49P23TIvg

Contributing User

Join Date: Aug 2011

Posts: 3,350

Time spent in forums: 1 Month 2 Weeks 3 Days 7 h 38 m 45 sec
Reputation Power: 383

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?

November 8th, 2012, 02: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, 02:34 PM

b49P23TIvg

Contributing User

Join Date: Aug 2011

Posts: 3,350

Time spent in forums: 1 Month 2 Weeks 3 Days 7 h 38 m 45 sec
Reputation Power: 383

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.

#11

November 8th, 2012, 02: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.

Prime Number Engine (Sieve)

Developer Shed Advertisers and Affiliates