Python Program to Check Prime Number

Write a Python program that takes in a number and checks whether it is a prime number.

A prime number is a natural number greater than 1 that has no divisors other than 1 and itself. In simpler terms, a prime number cannot be evenly divided by any other number except 1 and itself. Classic examples of prime numbers include 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, and so on.

To check if a number is prime, follow these steps:

1. Begin by taking a number as input from the user.
2. Then, start counting through natural numbers, beginning at 2.
3. Check whether the input number can be divided evenly by any of these natural numbers.
4. If the input number is divisible by any of these numbers, it is not a prime number; otherwise, it is a prime number.
5. Finally, exit the program.

There are several techniques to write a Python program for finding prime numbers. Let’s explore some of these methods:

• Prime Number Program in Python using For Loop
• Prime Number Program in Python using Recursion
• Python Program to Find Prime Numbers in a Given Range
• Prime Number Program in Python using Sieve of Eratosthenes

In this method, we determine whether a given number is prime by iterating from 2 to half of the number and checking for divisibility. If the number is divisible by any of these numbers, it is not prime.

Here is source code of the Python Program to check if a number is a prime number. The program output is also shown below.

# Prime Number Program in Python using For Loop
 
a=int(input("Enter number: "))
k=0
for i in range(2,a//2+1):
    if(a%i==0):
        k=k+1
if(k<=0):
    print("Number is prime")
else:
    print("Number isn't prime")

1. The user is prompted to enter the number to be checked and it is stored in a variable.
2. The variable k is initialized to 0.
3. A for loop ranges from 2 to half of the number, excluding 1 and the number itself to avoid counting them as divisors.
4. An if statement checks for divisors of the number by verifying if the remainder is equal to 0.
5. The k variable counts the number of divisors, and if it remains less than or equal to 0, the number is considered prime.
6. If k is greater than 0, the number is not prime.
7. The final result is then printed.

Time Complexity: O(n)
The program iterates from 2 to the given number divided by 2, resulting in a time complexity of O(n/2), which simplifies to O(n).

Space Complexity: O(1)
The program uses a constant amount of memory, regardless of the input size, resulting in a space complexity of O(1).

Testcase 1: In this case, we input the number “7” to check if it is a prime number.

Enter number: 7
Number is prime

Testcase 2: In this case, we input the number “35” to check if it is a prime number.

Enter number: 35
Number isn't prime

In this approach, the program determines whether a given number is prime or not using recursion.

Here is source code of the Python Program to find if a number is prime or not using recursion. The program output is also shown below.

def check(n, div = None):
    if div is None:
        div = n - 1
    while div >= 2:
        if n % div == 0:
            print("Number not prime")
            return False
        else:
            return check(n, div-1)
    else:
        print("Number is prime")
        return 'True'
n=int(input("Enter number: "))
check(n)

1. The program defines a recursive function called “check” to determine if a number is prime.
2. It checks if the number is divisible by a decreasing sequence of numbers starting from “n-1”.
3. If it finds a divisor, it prints “Number not prime” and returns False.
4. If no divisor is found, it prints “Number is prime” and returns ‘True’.
5. The program prompts the user to enter a number and calls the “check” function with the provided number as input.

Time Complexity: O(sqrt(n))
The time complexity of the program is O(sqrt(n)) because the loop iterates up to sqrt(n) to check for divisors.

Space Complexity: O(1)
The space complexity is O(1) because the program uses a constant amount of memory regardless of the input size.

Testcase 1: In this case, we enter the number “13” as input to check whether it is a prime number or not.

Enter number: 13
Number is prime

Testcase 2: In this case, we enter the number “30” as input to check whether it is a prime number or not.

Enter number: 30
Number not prime

In this method, the program takes in the upper limit and prints all prime numbers within the given range.

Here is source code of the Python Program to print all the prime numbers within a given range. The program output is also shown below.

r=int(input("Enter upper limit: "))
for a in range(2,r+1):
    k=0
    for i in range(2,a//2+1):
        if(a%i==0):
            k=k+1
    if(k<=0):
        print(a)

1. User must enter the upper limit of the range and store it in a different variable.
2. The first for loop ranges till the upper limit entered by the user.
3. The count variable is first initialized to 0.
4. The for loop ranges from 2 to the half of the number so 1 and the number itself aren’t counted as divisors.
5. The if statement then checks for the divisors of the number if the remainder is equal to 0.
6. The count variable counts the number of divisors and if the count is lesser or equal to 0, the number is a prime number.
7. If the count is greater than 0, the number isn’t prime.
8. The final result is printed.

Time and Space Complexity:
The time complexity of the given code is O(r²) because it checks divisibility for each number in the range from 2 to ‘r’. The space complexity is O(1) as it uses a fixed amount of memory regardless of the input size.

Testcase 1: This test inputs an upper limit of 15 and expects the program to find and display prime numbers within the range from 2 to 15.

Enter upper limit: 15
2
3
5
7
11
13

Testcase 2: In this case we inputs an upper limit of 40 and expects the program to find and display prime numbers within the range from 2 to 40.

Enter upper limit: 40
2
3
5
7
11
13
17
19
23
29
31
37

In this method, the program takes a range and prints prime numbers in that range using Sieve of Eratosthenes.

1. Take the value of n from the user.
2. Initialise the sieve with numbers from 2 to n.
3. Use a while loop with the condition that the sieve is not empty
4. Get the smallest number that is prime
5. Remove that number and it’s multiples
6. Continue till the sieve is empty
7. Exit

Here is the source code of the Python Program to takes a range and print prime numbers in that range using Sieve of Eratosthenes. The program output is also shown below.

n=int(input("Enter upper limit of range: "))
sieve=set(range(2,n+1))
while sieve:
    prime=min(sieve)
    print(prime,end="\t")
    sieve-=set(range(prime,n+1,prime))
 
print()

1. User enters the upper limit ‘n’ for the range.
2. A sieve is initialized as a set containing numbers from 2 to ‘n’ (inclusive).
3. A while loop is used to iterate until the sieve is not empty.
4. The variable ‘prime’ stores the smallest prime number from the sieve, which is then printed.
5. All multiples of the prime number are removed from the sieve.
6. Steps 4 and 5 are repeated until the sieve becomes empty.

Time Complexity: The time complexity of this code is O(n log log n) because the Sieve of Eratosthenes algorithm iteratively eliminates multiples of prime numbers, which results in a non-linear time complexity.

Space Complexity: The space complexity is O(n) because the code uses a set to store numbers from 2 to n, requiring linear space.

 
Case 1:
Enter upper limit of range: 10
2	3	5	7	
 
Case 2:
Enter upper limit of range: 15
2	3	5	7	11	13

To practice programs on every topic in Python, please visit “Programming Examples in Python”.