Trying to find the prime numbers using Python

Question

Below is my code to find the prime number using Python which is not working. Here the function prime will take an integer as input and return whether its a prime number or not. Could you please sort out the problem and explain it.

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

I think i have sorted out the first issue, the first "if" statement should be if x == 0 or x == 1. Now what about the rest.

In your first `if` statement you check if `x == 0` or if `1 != 0`. This will always return `True`. — Holloway, Jan 01 '15 at 11:40
looks like it'd work. In general it's useful to leave the question uncorrected as it keeps it as a valid question. As it stands it's a question about why working code doesn't work. — Holloway, Jan 01 '15 at 11:45
no. the `return true` is still in the wrong place, check if 9 is prime. — Jasen, Jan 01 '15 at 11:47
@Jasen good point. I missed that after seeing the first `if` — Holloway, Jan 01 '15 at 11:52
A mathematician, physicist, and engineer are taking a math test. One question asks "Are all odd numbers prime?" The mathematician thinks, "3 is prime, 5 is prime, 7 is prime, 9 is not prime -- nope, not all odd numbers are prime." The physicist thinks, " 3 is prime, 5 is prime, 7 is prime, 9 is not prime -- that could be experimental error -- 11 is prime, 13 is prime, yes, they're all prime." The engineer thinks, " 3 is prime, 5 is prime, 7 is prime, 9 is prime, 11 is prime, ..." — Jasen, Jan 01 '15 at 11:53

score 1 · Answer 1 · edited May 23 '17 at 12:07

What does your for loop?

if x % n == 0:
    return False
else:
    return True

^{which by the way eqals return bool(x % n)}

So, you return in first iteration, when n == 2.

The whole for loop equals return bool(x % 2), which simply checks if x is diviseable by 2.
That's not what you want.

So, what do you want?

You want to check if x is not diviseable by any numer from range(2, x).

You know that x is not prime, if you find one n from range(2, x), for which x % n == 0 is True.
You know that x is prime, when there is no n in range(2, x), for which x % n == 0 is True.

When can you say that none of n from range is a divisor of x?
After checking all ns from range!

After is the key here.
After the loop, in which you try to find divisor, you can only tell that x is prime.

I hope you now understand the code others posted without explanation.

Note: alternative syntax

Code others posted is correct. However, in Python there is second way writing the for, using for .. else:

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

Now i understand it clearly. Thank you very much. Also thanks for the **for..else**. — heemayl, Jan 01 '15 at 12:22
Why would you use the `for .. else` construct here? Without any break statements inside the `for` loop, the `else` is redundant - just place the `return True` at the same indentation level as the initial `for` loop. — Mark Dickinson, Jan 01 '15 at 13:36
@Mark: you're right. I mentioned `for .. else`, because the difference between oriniginal code and this with `for .. else` is just `else`'s and `return True`'s indention level. — GingerPlusPlus, Jan 01 '15 at 20:04

Jasen · Accepted Answer · 2015-01-01T12:30:27.080

The problem is that the return true should not happen until the for loop has completed.

what we have in the original code is a cuple of tests for trivial cases (x less than 3) and then a loop for testing all the larger numbers.

In the loop an attempt is made to divide x by a smaller number (starting with 2) and then if it divides evenly False is returned, if it does not True is returned, that is the mistake, instead of returning true, the loop should be allowed to repeat, and division should be tried again with the next number, and only after the supply of divisors (from the for loop) has been exhausted should true be returned.

here's a fixed version:

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

        return True

Others have commented that the loop need not continue all the way up to x and that stopping at sqrt(x) is sufficient, they are correct. doing that will make it faster in almost all cases.

Another speed up can be had if you have a list of small primes (upto sqrt(x)) - you need only test divisibility by the primes below sqrt(x),and not every integer in that range.

Its working. Could you please explain the last **return True** a bit broadly. — heemayl, Jan 01 '15 at 12:07

score 0 · Answer 3 · answered Dec 31 '17 at 09:51

The below code is for finding the prime number from 2 to nth number. For an example, the below code will print the prime number from 2 to 50 and also it will print the number in between 2 to 5o which is not prime.

import time
i=2
j=2
count=0
while(i<50):
 while (i>j):
    if (i%j)==0:
      count=count+1
      j=j+1
    else:
      j=j+1
 if count==0:
    print i," is a prime"
 else:
    print i," is not a prime"
 i=i+1
 j=2
 count=0
 time.sleep(2)

Trying to find the prime numbers using Python

3 Answers3

So, what do you want?

Note: alternative syntax

Linked