Detecting primes -- both "if" and "else" branches run in a loop, but only one should

Question

import math
while True:
 n=(raw_input("Please enter a number to check if it is prime or not " ))
 if n == "gate":
    exit()
 n=int(n)
 x=int( math.sqrt(n))
 if n%2==0:
    print n , "is an even number"
 else:
    for i in range(3,x+1,2):
        if n%i==0 :
           print " Composite",n, "div by" ,i ,"."
        else:
           print "PRIME"

This code runs fine if I enter an even but acts abnormal when I input an odd or prime integer. It identifies composite accurately. Irrespective of prime or composite odd it prints PRIME many times.(sometimes twice or thrice). The output is like:

Please enter a number to check if it is prime or not  53
PRIME
PRIME
PRIME
Please enter a number to check if it is prime or not  36
36 is an even number
Please enter a number to check if it is prime or not  21
Composite 21 div by 3 .
Please enter a number to check if it is prime or not  23
PRIME
Please enter a number to check if it is prime or not  37
PRIME
PRIME
Please enter a number to check if it is prime or not

I think I have done some indentation error or implemented while loop incorrectly. please help.

This question is not just about an algorithm for primality test but this addresses an implementation problem.

see [else on for loop](https://stackoverflow.com/questions/9979970/why-does-python-use-else-after-for-and-while-loops) — Tadhg McDonald-Jensen, Dec 29 '17 at 19:17

score 1 · Answer 1 · answered Dec 29 '17 at 19:21

1

You need to exit the loop when a factor is found, and print that the number is prime only after all factors have been tested. So your loop should look more like this:

for i in range(3, x + 1, 2):
    if not n % i:
       print " Composite", n, "div by" , i ,"."
       break      # exit loop explicitly
else:             # execute only if we didn't break out of loop
   print "PRIME"

Note that the else lines up with the for, not with the if.

answered Dec 29 '17 at 19:21

kindall

178,883
35
278
309

Thank you for help.Your code does the task perfectly. But can you explain what is the if for that else. It seems to be an else without if under previous else. – Sandipan Manna Dec 29 '17 at 19:39
As noted in the comment, the `else` is executed only if we didn't break out of the `for` loop. The `else` goes with the `for` not the `if`. [Documentation on use of `else` with loops](https://docs.python.org/3/tutorial/controlflow.html#break-and-continue-statements-and-else-clauses-on-loops).. Using `for`/`else` avoids the need to use a flag as some other solutions do. – kindall Dec 29 '17 at 19:44

score 0 · Accepted Answer · answered Dec 29 '17 at 19:13

You print "PRIME" as soon as the current i does not n, but you should only output "PRIME" if no i divides n. You can do it like this:

import math
while True:
 n=(raw_input("Please enter a number to check if it is prime or not " ))
 if n == "gate":
    exit()
 n=int(n)
 x=int( math.sqrt(n))
 if n%2==0:
    print n , "is an even number"
 else:
    prime = True
    for i in range(3,x+1,2):
        if n%i==0 :
           print " Composite",n, "div by" ,i ,"."
           prime = False
    if prime:
        print "PRIME"

Thank you very much. It solved my problem. – Sandipan Manna Dec 29 '17 at 19:31 — Sandipan Manna, Dec 29 '17 at 19:31

Detecting primes -- both "if" and "else" branches run in a loop, but only one should

2 Answers2