python code giving wrong output

Question

I have written the below code in python to print out prime numbers but its giving output like:

3,5,7,**9**,11,13,**15**,17,19,**21**,23,25............99

below is the code:

def isprime(n):
    if n == 1:
        return False
    for x in range(2, n):
        if n % x == 0:
            return False
        else:
            return True

def primes(n = 1):
    while(True):
        if isprime(n): yield n
        n += 1
for n in primes():
    if n > 100: break
    print(n)

@starf: I think it's pretty clear. The list of primes contains numbers that are not primes. Rahul was expecting prime numbers only. — Steven Rumbalski, Mar 11 '16 at 21:15

score 4 · Answer 1 · answered Mar 11 '16 at 21:06

4

You are returning True after the number fails to be divisible by one number. You need to return true after you have checked all the numbers. Instead, you should write

def isprime(n):
    if n == 1:
        return False
    for x in range(2, n):
        if n % x == 0:
            return False

    return True

One other note: if you are testing for prime numbers, you only need to test up to the square root of the number. If the number is not divisible by any numbers less than its square root, then it is also is not divisible by any that are greater and thus must be prime. This will help make your code more efficient.

answered Mar 11 '16 at 21:06

Erik Godard

5,930
6
30
33

1

Also, it's worthwhile to treat `n == 2` as a special case and then only test for odd factors in the loop. – PM 2Ring Mar 11 '16 at 21:10
Indeed. Also, something like a [Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) would best for finding all primes below a given value. – Erik Godard Mar 11 '16 at 21:12
1

[Definitely](http://stackoverflow.com/a/26193172/4014959)! Or [this](http://stackoverflow.com/a/26440674/4014959) for primes in a given range. For a comparison of various prime sieving algorithms in Python, see [Fastest way to list all primes below N](http://stackoverflow.com/a/26440674/4014959). And for testing individual large numbers for primality there's [Miller-Rabin](http://math.stackexchange.com/a/1638487/207316)... but that might be a getting a bit too advanced for the OP. :) – PM 2Ring Mar 11 '16 at 21:39

score 1 · Answer 2 · answered Mar 11 '16 at 21:06

Your isprime function says:

for x in range(2, n):
    if n % x == 0:
        return False
    else:
        return True

This means that on the first iteration (when x==2), if n%x is not zero, it will return True. So it will return True for any odd number (above 1, which you skipped).

Instead, you want to return True if none of the numbers in the loop were factors.

for x in range(2, n):
    if n % x == 0:
        return False
# the loop finished without returning false, so none of the numbers was a factor
return True

python code giving wrong output

2 Answers2