Python prime listing error

Question

n = int(input("input n"))
prime = [2]
base = 3
order = 0

while base < n + 1:
    if order < len(prime):
        if base % prime[order] == 0:
            order = len(prime)
        else:
            order += 1
    else:
        prime.append(base)
    order = 0
    base += 1
print (prime)

I am trying to create a list of prime numbers from 1 to given number 'n'. (ignoring the case for numbers less than 3)

What I intend to do is:

bring first number from 3 to n (let's call this base)
compare base to first number in prime list (in this case, 2)
if the base is not divisible, compare this to next number in prime list.
repeat step 3 until all numbers in the prime list are compared or at least one number divisible to base in the prime list appears.
if base compared to all numbers in the prime list and is not divisible by any of them, append base to prime list.
increase the value of base by 1 and repeat step 2 to 5 upto base = n.

Whatever the value i put for n, i only get single value of 2 in the prime list printed. Please help to find out which part is wrong.

Possible duplicate of [Sieve Of Atkin Implementation in Python](http://stackoverflow.com/questions/21783160/sieve-of-atkin-implementation-in-python) — Confusion Matrix, Apr 26 '17 at 00:47

score 0 · Accepted Answer · answered Apr 26 '17 at 00:48

The reason your code is failing is because you are not actually checking through all of the stored prime numbers correctly - you need a second loop for this. Fortunately, Python makes this easy for you in two different ways: A list of values can be easily looped through, and else is supported by for. The modified code should look something like this:

n = int(input("input n"))
prime = [2]
base = 3

while base < n + 1:
    for p in prime:
        if base % p == 0:
            # base is NOT a prime, break out
            break
    else:
        # loop ran to completion
        prime.append(base)
    base += 1
print (prime)

So instead of some other if statement that doesn't quite do what you think it does, we instead use a for loop check all values in the prime list (assign that to p) and do the division as you might expect. If the modulus is 0, the loop breaks uncleanly and the else block will not run, and if none of the primes result in a modulus of 0 the else block will be triggered, adding that newly discovered prime number to the list and so on.

Example:

$ python3 foo.py
input n19
[2, 3, 5, 7, 11, 13, 17, 19]

If you wish to keep the existing logic (i.e. no for loops), you can do another while loop inside and remember to set order to 0 before it.

@KimKihyun you're welcome. Generally homework type questions like these will get looked at if we can see an honest attempt at it, so keep up the good work. — metatoaster, Apr 26 '17 at 01:01

Python prime listing error

1 Answers1