#1
  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. #2
  3. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2012
    Location
    39N 104.28W
    Posts
    158
    Rep Power
    3
    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)
  4. #3
  5. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,894
    Rep Power
    481
    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!
  6. #4
  7. Commie Mutant Traitor
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Jun 2004
    Location
    Alpharetta, GA
    Posts
    1,806
    Rep Power
    1570
    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
  8. #5
  9. 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:
                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!!!
  10. #6
  11. 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!
  12. #7
  13. 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!
  14. #8
  15. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,894
    Rep Power
    481
    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!
  16. #9
  17. 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?
  18. #10
  19. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,894
    Rep Power
    481
    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!
  20. #11
  21. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

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

IMN logo majestic logo threadwatch logo seochat tools logo