Python Program to Check Prime Number

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: for i in range(2, int(n**0.5) + 1): if n % i == 0: return False.

Examples

Input2

Output2 is a prime number

Input15

Output15 is not a prime number

Input1

Output1 is not a prime number

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 not prime.

3

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

4

If any divisor divides the number evenly, return not prime.

5

If no divisors found, return 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

num = int(input("Enter a number: "))
if is_prime(num):
    print(f"{num} is a prime number")
else:
    print(f"{num} is not a prime number")

Output

Enter a number: 17
17 is a prime number

Dry Run

Let's trace the number 17 through the code to see how it checks for primality.

1

Check if number <= 1

17 is greater than 1, so continue.

2

Loop from 2 to sqrt(17)

Check divisors 2, 3, and 4 (since int(sqrt(17)) + 1 = 5).

3

Check divisibility

17 % 2 != 0, 17 % 3 != 0, 17 % 4 != 0, so no divisors found.

4

Return result

No divisors found, so 17 is prime.

i	n % i	Divides evenly?
2	17 % 2 = 1	No
3	17 % 3 = 2	No
4	17 % 4 = 1	No

Why This Works

Step 1: Check if number is less than or equal to 1

Numbers less than or equal to 1 are not prime by definition, so we return False immediately.

Step 2: Loop up to square root

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

Step 3: Check divisibility

If the number divides evenly by any number in the loop, it means it has a divisor other than 1 and itself, so it is not prime.

Step 4: Return True if no divisors found

If no divisors are found, the number is prime, so we 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))

num = int(input("Enter a number: "))
print(f"{num} is {'a prime' if is_prime(num) else 'not a prime'} number")

This method is concise and uses Python's all() function, but may be less clear for beginners.

Check divisibility by 2 separately and then odd numbers only

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

num = int(input("Enter a number: "))
print(f"{num} is {'a prime' if is_prime(num) else 'not a prime'} number")

This method is more efficient by skipping even numbers after checking 2.

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

Time Complexity

The loop runs up to the square root of n, so the time complexity is O(√n). This is because any factor larger than the square root would have a corresponding smaller factor already checked.

Space Complexity

The program uses a constant amount of extra space, O(1), as it only stores a few variables and does not use additional data structures.

Which Approach is Fastest?

The method checking divisibility by 2 separately and then only odd numbers is faster than checking all numbers. The all() function method is concise but similar in speed.

Approach	Time	Space	Best For
Basic loop up to sqrt(n)	O(√n)	O(1)	Simplicity and clarity
all() with generator	O(√n)	O(1)	Concise Pythonic code
Check 2 then odds only	O(√n/2)	O(1)	Better performance for large numbers