Python Program to Check Prime Number

mediumLoops with elsePython

A prime number has exactly two divisors: 1 and itself. This version is fast because it only tries divisors up to the square root.

The question

Read an integer n (n > 1) and print whether it is a prime number or not a prime number.

The code

program.py

n = int(input())
for i in range(2, int(n ** 0.5) + 1):
    if n % i == 0:
        print(n, "is not a prime number")
        break
else:
    print(n, "is a prime number")

Try it Yourself »

Input

Output

21 is not a prime number

How it works

1If n has a divisor bigger than √n, it also has one smaller than √n — so checking up to int(n ** 0.5) is enough.
2If any i divides n exactly (n % i == 0), n is not prime and break stops the loop.
3A for loop's else block runs only if the loop finished without break — that means no divisor was found, so n is prime.

Common mistakes

Putting else under the if instead of under the for — it then prints "prime" for every number that does not divide on the first try.
Forgetting that 1 is not a prime number.

Now solve a similar question yourself

A new Python question every time, checked instantly.

Practice questions

Previous Next