Prime Number Program in Python

The question

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

The code

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")

How it works

1. 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.
2. 2If any i divides n exactly (n % i == 0), n is not prime and break stops the loop.
3. 3A for loop's else block runs only if the loop finished without break — that means no divisor was found, so n is prime.

Dry run: is 21 a prime number?

int(21 ** 0.5) + 1 is 5, so range(2, 5) gives i = 2, 3 and 4 at most.

The loop broke, so the else block is skipped: 21 is not a prime number (21 = 3 × 7).

Prime number in Python using a function

The function returns False as soon as it finds a divisor and handles n < 2 too, which the short version above does not need because the question says n > 1.

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

n = int(input())
if is_prime(n):
    print(n, "is a prime number")
else:
    print(n, "is not a prime number")

29

29 is a prime number

Print all prime numbers from 1 to 50

Call the same check for every number in the range and print the ones that pass, on one line.

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

print(*[n for n in range(1, 51) if is_prime(n)])

(no input)

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

Questions students ask

Is 1 a prime number?

No. A prime number must have exactly two different divisors, and 1 has only one. That is why the function version returns False for any n below 2.

Why check divisors only up to the square root?

Divisors come in pairs: if 3 × 7 = 21, one of the pair is always at most √21 ≈ 4.6. If no number up to the square root divides n, none above it can either — so for 1,000,003 the loop runs about 1,000 times instead of a million.

What does the else after the for loop do?

In Python a for loop can have an else block. It runs only when the loop finishes without a break. Here break means a divisor was found, so the else ("is a prime number") runs only when there was none.