How to check if a number is prime in Python

How to check if a number is prime in Python.

Here is a step-by-step tutorial on how to check if a number is prime in Python:

Step 1: Understand Prime Numbers

Before we begin, let's understand what prime numbers are. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. For example, 2, 3, 5, 7, 11, 13, etc., are prime numbers.

Step 2: Get Input from User

To check if a number is prime, we need to take input from the user. Let's write code to get the number from the user:

num = int(input("Enter a number: "))

This code prompts the user to enter a number and stores it in the variable num. We convert the input to an integer using int().

Step 3: Implement the Prime Checking Algorithm

Now, let's write the code to check if the number is prime or not. We'll use a simple algorithm that iterates through all numbers from 2 to the square root of the input number and checks if any of them divide the input number evenly.

is_prime = True

if num < 2:
    is_prime = False
else:
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            is_prime = False
            break

In this code, we initialize a boolean variable is_prime to True. We then check if the number is less than 2; in that case, it cannot be prime, so we set is_prime to False. Otherwise, we iterate through all numbers from 2 to the square root of the input number (int(num**0.5) + 1). For each number, if it divides the input number (num) evenly (num % i == 0), we set is_prime to False and break out of the loop using the break statement.

Step 4: Display the Result

Finally, let's display the result to the user based on the value of is_prime:

if is_prime:
    print(num, "is a prime number.")
else:
    print(num, "is not a prime number.")

This code checks the value of is_prime. If it is True, it prints that the number is prime. Otherwise, it prints that the number is not prime.

Complete Code

Here's the complete code for checking if a number is prime:

num = int(input("Enter a number: "))

is_prime = True

if num < 2:
    is_prime = False
else:
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            is_prime = False
            break

if is_prime:
    print(num, "is a prime number.")
else:
    print(num, "is not a prime number.")

Additional Optimizations

The above code works correctly, but there are a few optimizations we can make to improve its efficiency:

1. We only need to check divisibility up to the square root of the number, so we can stop the loop earlier by using int(num**0.5) + 1 as the upper limit.
2. We can skip even numbers (except 2) because they are divisible by 2. This can reduce the number of iterations by half.

Here's the optimized code:

num = int(input("Enter a number: "))

is_prime = True

if num < 2 or (num > 2 and num % 2 == 0):
    is_prime = False
else:
    for i in range(3, int(num**0.5) + 1, 2):
        if num % i == 0:
            is_prime = False
            break

if is_prime:
    print(num, "is a prime number.")
else:
    print(num, "is not a prime number.")

This code skips even numbers in the loop by starting the range at 3 and incrementing by 2 (range(3, int(num**0.5) + 1, 2)). It also checks if the number is divisible by 2 separately to handle the case where the input number is 2.

That's it! You now have a detailed tutorial on how to check if a number is prime in Python.