Python Prime number finder

Question

I have made a Prime number finder where you enter a number and it tells you weather it is a prime number.

while True:
    p = int(input('Enter a number '))
    for d in range(2, p):
        if p % d == 0:
            print(p, "is not a prime number!", d,"*", p//d,"=",p)
            break
        else:
            print(p, "is a prime number!")
            break

However it is displaying numbers that clearly aren't prime. I think it is only dividing it by 2 as all the odd numbers I have tried are being output as odd.

Can anyone help to fix this?

Think it through - when are you sure that a number is prime? Is it after you've checked whether it's divisible by two? — jonrsharpe, Apr 24 '16 at 16:58
I think it is only dividing it by 2 as all the odd numbers I have tried are being output as odd? — Avinash, Apr 24 '16 at 16:59
for performance, you can take `for d in range(2, math.sqrt(p)+1):` — S L, Apr 24 '16 at 20:31
related: [What is the best algorithm for checking if a number is prime?](http://stackoverflow.com/q/1801391/4279) — jfs, Apr 26 '16 at 07:29

Delgan · Accepted Answer · 2016-04-26T07:14:19.270

2

You have to check all the numbers before you can say it's prime. Currently, your loop exits at the first check (which is d == 2) and return False if p % 2 == 0, else True.

You should put the else statement at the end of the loop, like this:

while True:
    p = int(input('Enter a number '))
    for d in range(2, p):
        if p % d == 0:
            print(p, "is not a prime number!", d,"*", p//d,"=",p)
            break
    else:
        print(p, "is a prime number!")

The else is executed only if the loop did not end with break. This means that if not any divider was found, your number is prime.

Moreover, note that you do not have to check numbers until p, you can stop at sqrt(p) and iterate two by two: for d in range(3, int(p**0.5) + 1, 2).

edited Apr 26 '16 at 07:14

answered Apr 24 '16 at 16:59

Delgan

18,571
11
90
141

Thank you that worked perfectly, i'm not quite sure why I put the break in to the code in the first place. :) – User592 Apr 24 '16 at 17:04
1

Also, you don't need to check as high as `p`. Just do `for d in range(2, p ** 0.5 + 1):` – zondo Apr 24 '16 at 17:07
@User592 and also you should test 2, and then only the odd numbers ... no need to divide by `4,6,8,10,...` for more speed/ideas see [Prime numbers by Eratosthenes quicker sequential than concurrently?](http://stackoverflow.com/a/22477240/2521214) – Spektre Apr 26 '16 at 06:14

Python Prime number finder

1 Answers1