Python Program to Check if Number is Prime

You can check if a number is prime in Python by testing if it is greater than 1 and not divisible by any number from 2 up to its square root using a loop, for example: def is_prime(n): return n > 1 and all(n % i != 0 for i in range(2, int(n**0.5) + 1)).

Examples

Input2

OutputTrue

Input15

OutputFalse

Input17

OutputTrue

How to Think About It

To check if a number is prime, first understand that a prime number is greater than 1 and has no divisors other than 1 and itself. So, you test if the number can be divided evenly by any number starting from 2 up to the square root of the number. If you find any divisor, the number is not prime; otherwise, it is prime.

Algorithm

1

Get the input number.

2

If the number is less than or equal to 1, return False (not prime).

3

Check divisibility from 2 up to the square root of the number.

4

If any divisor divides the number evenly, return False.

5

If no divisors found, return True (number is prime).

Code

python

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

print(is_prime(2))
print(is_prime(15))
print(is_prime(17))

Output

True
False
True

Dry Run

Let's trace the number 15 through the code to see if it is prime.

1

Check if number is <= 1

15 is greater than 1, so continue.

2

Loop from 2 to sqrt(15)

Check divisors 2, 3 (since sqrt(15) ≈ 3.87).

3

Check divisibility by 2

15 % 2 != 0, so continue.

4

Check divisibility by 3

15 % 3 == 0, divisor found, return False.

Divisor	15 % Divisor	Is Divisible?
2	1	No
3	0	Yes

Why This Works

Step 1: Check number validity

A prime number must be greater than 1, so we return False immediately if not.

Step 2: Limit divisor checks

We only check divisors up to the square root because any larger factor would have a smaller complementary factor already checked.

Step 3: Return result

If no divisor divides the number evenly, the number is prime, so return True.

Alternative Approaches

Using all() with generator expression

python

def is_prime(n):
    return n > 1 and all(n % i != 0 for i in range(2, int(n**0.5) + 1))

print(is_prime(29))

This method is concise and Pythonic but may be less clear for beginners.

Check divisibility by 2 separately, then only odd numbers

python

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

print(is_prime(37))

This reduces checks by skipping even numbers after 2, improving efficiency for large numbers.

Complexity: O(√n) time, O(1) space

Time Complexity

The loop runs up to the square root of n, so the time grows roughly with √n.

Space Complexity

The program uses a fixed amount of extra space regardless of input size.

Which Approach is Fastest?

Checking only odd divisors after 2 is faster than checking all numbers; using all() with a generator is concise but similar in speed.

Approach	Time	Space	Best For
Simple loop up to sqrt(n)	O(√n)	O(1)	Clarity and beginners
all() with generator	O(√n)	O(1)	Concise Pythonic code
Check 2 then odds only	O(√n/2)	O(1)	Efficiency for larger numbers