Prime numbers are integers greater than 1 that have only two positive divisors: 1 and themselves. They hold significant importance in mathematics and computer science, finding applications in various algorithms and cryptographic systems. In this tutorial, you will learn how to write a **Python program to check whether a given number is prime** or not.

## What is a Prime Number?

Before diving into the Python code, let’s understand the concept of prime numbers. 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, etc., are prime numbers.

## Approach to Check Prime Numbers:

To determine whether a number is prime, we can follow a simple algorithm:

- If the number is less than or equal to 1, it’s not prime.
- If the number is 2, it’s prime.
- If the number is even (except 2), it’s not prime.
- Check for divisibility by odd numbers from 3 up to the square root of the number.

## Python Code to Check Prime Numbers:

Now, let’s implement the above algorithm in Python:

```
import math
def is_prime(num):
if num <= 1:
return False
elif num == 2:
return True
elif num % 2 == 0:
return False
else:
# Iterate through odd numbers up to the square root of num
for i in range(3, int(math.sqrt(num)) + 1, 2):
if num % i == 0:
return False
return True
# Test the function
number = int(input("Enter a number: "))
if is_prime(number):
print(number, "is a prime number")
else:
print(number, "is not a prime number")
```

```
Enter a number: 61
61 is a prime number
```

Explanation of the Code:

- The
`is_prime`

function takes a number as input and returns True if it’s prime and False otherwise. - It first handles edge cases where the number is less than or equal to 1, equal to 2, or even.
- Then, it iterates through odd numbers from 3 up to the square root of the number and checks for divisibility.
- If the number is divisible by any of these odd numbers, it returns False, indicating that the number is not prime. Otherwise, it returns True.

## Dealing with Large Numbers:

When dealing with large numbers, a more efficient approach is required for checking prime numbers. One such method is the **Miller-Rabin primality test,** which is **probabilistic but highly accurate**. Python’s sympy library provides an implementation of this test. Here’s how you can use it:

First, make sure you have `sympy`

installed. You can install it via pip if you haven’t already:

`pip install sympy`

Then, you can use the `sympy.isprime()`

function to check if a large number is prime. Here’s an example:

```
from sympy import isprime
# Check if a large number is prime
number = 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
if isprime(number):
print(number, "is a prime number")
else:
print(number, "is not a prime number")
```

This function is quite efficient even for large numbers. However, do note that sympy’s `isprime()`

function uses probabilistic methods for large numbers, so there’s a tiny chance it might return a false positive (very, very unlikely for large numbers). For cryptographic applications or situations where absolute certainty is required, you might need to employ deterministic primality tests, which are computationally more intensive.