Skip to content
Home » Blog » How to check a prime number in Python

How to check a prime number in Python

How to Check a Prime Number in Python – Complete Guide for Beginners

What is a Prime Number?

Let’s start with the basics. A prime number is like a special club member in math.

Think of it this way. Every number has friends who can divide it evenly. These friends are called “factors”.

A prime number is very picky. It only has two friends: the number 1 and itself.

Let me show you what this means with simple examples.

Understanding Through Examples

Let’s look at the number 7. Can any number divide 7 evenly?

  • 7 ÷ 1 = 7 (no remainder) ✓
  • 7 ÷ 2 = 3 remainder 1 ✗
  • 7 ÷ 3 = 2 remainder 1 ✗
  • 7 ÷ 4 = 1 remainder 3 ✗
  • 7 ÷ 5 = 1 remainder 2 ✗
  • 7 ÷ 6 = 1 remainder 1 ✗
  • 7 ÷ 7 = 1 (no remainder) ✓

Only 1 and 7 can divide 7 evenly. So 7 is prime!

Prime Numbers (The Special Ones)

  • 2 – Factors: 1, 2 (exactly 2 factors)
  • 3 – Factors: 1, 3 (exactly 2 factors)
  • 5 – Factors: 1, 5 (exactly 2 factors)
  • 7 – Factors: 1, 7 (exactly 2 factors)
  • 11 – Factors: 1, 11 (exactly 2 factors)

Non-Prime Numbers (Have More Friends)

Now let’s see numbers that have more than 2 factors:

  • 4 – Factors: 1, 2, 4 (3 factors = not prime)
  • 6 – Factors: 1, 2, 3, 6 (4 factors = not prime)
  • 8 – Factors: 1, 2, 4, 8 (4 factors = not prime)
  • 9 – Factors: 1, 3, 9 (3 factors = not prime)
  • 12 – Factors: 1, 2, 3, 4, 6, 12 (6 factors = not prime)

Visual Comparison: Prime vs Non-Prime

Click the image below to see a detailed comparison of prime and non-prime numbers:

Prime vs Non-Prime Factor Comparison

The Rule for Prime Numbers

Here’s the simple rule to remember:

  1. A prime number must be greater than 1
  2. It can only be divided evenly by 1 and itself
  3. It has exactly 2 factors – no more, no less

Why isn’t 1 a prime number?

The number 1 only has one factor: itself. Prime numbers need exactly 2 factors. So 1 doesn’t qualify.

Why is 2 special?

2 is the only even prime number. All other even numbers can be divided by 2, so they have more than 2 factors.

Understanding prime numbers helps us in programming. We use them in security, encryption, and many algorithms. You can learn more about Python type functions to work with different number types in your code.

Basic Method to Check Prime Numbers

Now let’s learn how to check if a number is prime using Python. We’ll start with the easiest method first.

Think of this like being a detective. We need to find out if a number has any secret factors hiding.

Algorithm Flowchart

Before we write code, let’s see how the algorithm works step by step:

Prime Number Algorithm Flowchart

The Detective Method (Step by Step)

Here’s our detective plan to catch any hidden factors:

Step 1: Quick Check

First, we check if the number is less than 2. Numbers like 0, 1, and negative numbers are automatically not prime.

Step 2: Start the Investigation

We start checking from number 2. Why 2? Because 1 always divides every number, so we skip it.

Step 3: Test Every Possible Suspect

We try dividing our number by every number from 2 up to the number minus 1.

Step 4: Look for Evidence

If any number divides evenly (remainder = 0), we found a factor! This means the number is not prime.

Step 5: Make the Final Decision

If we test all possible numbers and find no factors, the number is prime!

Let’s See This in Action

Let’s check if 13 is prime using our detective method:

  1. Quick Check: Is 13 ≥ 2? Yes! ✓
  2. Test 2: 13 ÷ 2 = 6 remainder 1 (not divisible) ✓
  3. Test 3: 13 ÷ 3 = 4 remainder 1 (not divisible) ✓
  4. Test 4: 13 ÷ 4 = 3 remainder 1 (not divisible) ✓
  5. Test 5: 13 ÷ 5 = 2 remainder 3 (not divisible) ✓
  6. Test 6: 13 ÷ 6 = 2 remainder 1 (not divisible) ✓
  7. Test 7: 13 ÷ 7 = 1 remainder 6 (not divisible) ✓
  8. Test 8: 13 ÷ 8 = 1 remainder 5 (not divisible) ✓
  9. Test 9: 13 ÷ 9 = 1 remainder 4 (not divisible) ✓
  10. Test 10: 13 ÷ 10 = 1 remainder 3 (not divisible) ✓
  11. Test 11: 13 ÷ 11 = 1 remainder 2 (not divisible) ✓
  12. Test 12: 13 ÷ 12 = 1 remainder 1 (not divisible) ✓

Result: No factors found! 13 is prime! 🎉

Now Let’s Check a Non-Prime Number

Let’s check if 12 is prime:

  1. Quick Check: Is 12 ≥ 2? Yes! ✓
  2. Test 2: 12 ÷ 2 = 6 remainder 0 (divisible!) ❌

Result: We found a factor (2)! 12 is not prime! We can stop here.

Python Code – Basic Method

Python
def is_prime_basic(number):
    """
    Check if a number is prime using basic method
    This method checks all numbers from 2 to number-1
    """
    # Numbers less than 2 are not prime
    if number < 2:
        return False
    
    # Check if any number from 2 to number-1 divides our number
    for i in range(2, number):
        if number % i == 0:
            return False  # Found a divisor, so not prime
    
    return True  # No divisor found, so it's prime

# Test the function with different numbers
test_numbers = [2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

print("Testing Basic Prime Checker:")
print("-" * 30)

for num in test_numbers:
    result = is_prime_basic(num)
    if result:
        print(f"{num} is a prime number")
    else:
        print(f"{num} is not a prime number")

Output:

Testing Basic Prime Checker:
------------------------------
2 is a prime number
3 is a prime number
4 is not a prime number
5 is a prime number
6 is not a prime number
7 is a prime number
8 is not a prime number
9 is not a prime number
10 is not a prime number
11 is a prime number

Understanding the Code Step by Step

Now let's break down each part of the code. I'll explain what every line does in simple words.

Part 1: Creating the Function

Python
def is_prime_basic(number):

This line creates a function. Think of a function like a machine.

You put a number into the machine. The machine tells you if it's prime or not.

The word def means "define a function". The name is_prime_basic is what we call our machine.

Learn more about defining and calling functions in Python.

Part 2: The Quick Safety Check

Python
if number < 2:
    return False

This part checks if the number is less than 2.

Remember: prime numbers start from 2. So 0, 1, and negative numbers are automatically not prime.

If the number is less than 2, we immediately say "False" (not prime) and stop.

This saves us time. No need to do more checking!

Part 3: The Main Detective Work

Python
for i in range(2, number):
    if number % i == 0:
        return False

This is where the real detective work happens. Let me explain line by line:

Line 1: for i in range(2, number):

This creates a loop. It means "try every number from 2 up to our number minus 1".

For example, if our number is 7, it tries: 2, 3, 4, 5, 6.

Learn more about for loops in Python.

Line 2: if number % i == 0:

The % symbol is the "remainder operator". It tells us what's left after division.

For example: 7 % 3 = 1 (because 7 ÷ 3 = 2 remainder 1)

If the remainder is 0, it means the division is exact. We found a factor!

Line 3: return False

If we find any factor, we immediately say "False" (not prime) and stop.

No need to check more numbers. We already found proof it's not prime!

Part 4: The Final Verdict

Python
return True

If we check all possible numbers and don't find any factors, we reach this line.

This means the number is prime! We return "True".

Why This Method is Slow

This method works perfectly, but it can be very slow. Here's why:

Imagine you want to check if 1,000,000 is prime.

The computer has to test 999,998 different numbers!

That's like counting from 2 to 999,999. It takes a very long time.

For small numbers (like 2 to 100), this method is fine.

For big numbers, we need smarter methods. We'll learn those next!

Visual Flowchart

Want to see how this algorithm flows? Click the image below to view the detailed flowchart:

Prime Number Algorithm Flowchart

For learning more advanced programming techniques, check out these hidden Python libraries for machine learning.

Improved Method with Square Root

Great! Now you understand the basic method. But there's a problem - it's too slow for big numbers.

Let me teach you a clever trick that makes our prime checker much faster!

The Amazing Square Root Discovery

Here's a mathematical secret that will blow your mind:

We don't need to check ALL numbers up to our target number. We only need to check up to the square root!

But why does this work?

Let me explain with a simple example that even a 5th grader can understand.

Understanding with a Simple Example

Let's say we want to check if 36 is prime.

The Old Way (Basic Method):

We would check: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35

That's 34 numbers to check! 😱

The New Way (Square Root Method):

Square root of 36 is 6. So we only check: 2, 3, 4, 5, 6

That's only 5 numbers! 🎉

The Magic Behind This:

When we find that 6 divides 36, we get: 36 ÷ 6 = 6

But we also automatically know that 6 × 6 = 36

So if there was a bigger factor (like 12), there would also be a smaller factor (like 3)

Since we already checked all smaller factors, we don't need to check the bigger ones!

Let's See This Magic in Action

Let's check if 25 is prime using our new smart method:

Step 1: Find the square root of 25

√25 = 5

Step 2: Only check divisors from 2 to 5

  • 25 ÷ 2 = 12 remainder 1 (not divisible) ✓
  • 25 ÷ 3 = 8 remainder 1 (not divisible) ✓
  • 25 ÷ 4 = 6 remainder 1 (not divisible) ✓
  • 25 ÷ 5 = 5 remainder 0 (divisible!) ❌

Result: We found a factor (5)! 25 is not prime!

Time Saved: Instead of checking 23 numbers, we only checked 4!

Testing with a Prime Number

Let's check if 17 is prime:

Step 1: Find the square root of 17

√17 ≈ 4.12, so we check up to 4

Step 2: Check divisors from 2 to 4

  • 17 ÷ 2 = 8 remainder 1 (not divisible) ✓
  • 17 ÷ 3 = 5 remainder 2 (not divisible) ✓
  • 17 ÷ 4 = 4 remainder 1 (not divisible) ✓

Result: No factors found! 17 is prime!

Time Saved: Instead of checking 15 numbers, we only checked 3!

Python Code - Improved Method

Python
import math

def is_prime_improved(number):
    """
    Check if a number is prime using square root optimization
    This method only checks up to the square root of the number
    """
    # Numbers less than 2 are not prime
    if number < 2:
        return False
    
    # Special case: 2 is prime
    if number == 2:
        return True
    
    # Even numbers greater than 2 are not prime
    if number % 2 == 0:
        return False
    
    # Check odd divisors up to square root
    for i in range(3, int(math.sqrt(number)) + 1, 2):
        if number % i == 0:
            return False
    
    return True

# Test the improved function
test_numbers = [2, 3, 4, 5, 25, 29, 97, 100, 101]

print("Testing Improved Prime Checker:")
print("-" * 35)

for num in test_numbers:
    result = is_prime_improved(num)
    sqrt_limit = int(math.sqrt(num)) + 1
    
    if result:
        print(f"{num} is prime (checked up to {sqrt_limit})")
    else:
        print(f"{num} is not prime (checked up to {sqrt_limit})")

Output:

Testing Improved Prime Checker:
-----------------------------------
2 is prime (checked up to 2)
3 is prime (checked up to 2)
4 is not prime (checked up to 3)
5 is prime (checked up to 3)
25 is not prime (checked up to 6)
29 is prime (checked up to 6)
97 is prime (checked up to 10)
100 is not prime (checked up to 11)
101 is prime (checked up to 11)

How This Improved Code Works

1. Import Math Module

Python
import math

We import the math module to use the sqrt() function for square root calculation.

2. Handle Special Cases

Python
if number == 2:
    return True

if number % 2 == 0:
    return False

We handle 2 separately because it's the only even prime number. All other even numbers are not prime.

3. Check Only Odd Numbers

Python
for i in range(3, int(math.sqrt(number)) + 1, 2):

This loop starts at 3 and checks only odd numbers. The 2 at the end means "step by 2" (skip even numbers). We only go up to the square root of the number.

Speed Improvement

This method is much faster! For a number like 1,000,000:

  • Basic method: checks 999,998 numbers
  • Improved method: checks only about 500 numbers
  • That's about 2000 times faster!

Advanced Optimized Method

Wow! You've learned the square root trick. But wait - there's an even faster way!

Professional programmers use super-smart tricks to make prime checking lightning fast.

Complete Concept Mind Map

Before we dive into the advanced method, let's see the big picture of all prime number concepts:

Prime Numbers Mind Map

The Super Smart Tricks

The advanced method uses several clever tricks. Let me explain each one simply:

Trick 1: Pre-Made Answer List

For very small numbers, we already know the answer. Why calculate when we can just look it up?

It's like having a cheat sheet for numbers 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31.

Trick 2: Skip All Even Numbers

Think about it: every even number (except 2) can be divided by 2.

So we only need to check 2 once, then skip all other even numbers!

Trick 3: The 6k±1 Magic Rule

Here's a mathematical secret: All prime numbers greater than 3 follow a special pattern.

They are always 1 more or 1 less than a multiple of 6!

For example:

  • 5 = 6×1 - 1
  • 7 = 6×1 + 1
  • 11 = 6×2 - 1
  • 13 = 6×2 + 1
  • 17 = 6×3 - 1
  • 19 = 6×3 + 1

This means we can skip many numbers and only check the special ones!

How Much Faster Is This?

Let's see the amazing difference:

To check if 1,000,000 is prime:

  • Basic Method: Check 999,998 numbers
  • Square Root Method: Check about 1,000 numbers
  • Advanced Method: Check about 166 numbers!

The advanced method is about 6,000 times faster than the basic method!

Python Code - Advanced Method

Python
import math
import time

def is_prime_advanced(number):
    """
    Advanced prime checking with multiple optimizations
    - Handles small numbers with lookup
    - Skips even numbers
    - Uses efficient divisibility testing
    """
    # Handle small numbers with pre-computed results
    if number < 2:
        return False
    if number in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]:
        return True
    if number < 32:
        return False
    
    # Quick checks for divisibility by small primes
    if number % 2 == 0 or number % 3 == 0 or number % 5 == 0:
        return False
    
    # Check for divisibility by numbers of the form 6k ± 1
    limit = int(math.sqrt(number)) + 1
    for i in range(7, limit, 6):
        if number % i == 0 or number % (i + 4) == 0:
            return False
    
    return True

def check_multiple_methods(number):
    """
    Compare all three methods for a given number
    """
    print(f"\nChecking if {number} is prime using all methods:")
    print("=" * 50)
    
    # Basic method (with timing)
    start_time = time.time()
    result_basic = is_prime_basic(number) if number < 10000 else "Skipped (too slow)"
    basic_time = time.time() - start_time
    
    # Improved method (with timing)
    start_time = time.time()
    result_improved = is_prime_improved(number)
    improved_time = time.time() - start_time
    
    # Advanced method (with timing)
    start_time = time.time()
    result_advanced = is_prime_advanced(number)
    advanced_time = time.time() - start_time
    
    print(f"Basic method:    {result_basic} (Time: {basic_time:.6f} seconds)")
    print(f"Improved method: {result_improved} (Time: {improved_time:.6f} seconds)")
    print(f"Advanced method: {result_advanced} (Time: {advanced_time:.6f} seconds)")
    
    return result_advanced

# Test with different sized numbers
test_numbers = [97, 1009, 10007, 100003]

for num in test_numbers:
    check_multiple_methods(num)

Output:

Checking if 97 is prime using all methods:
==================================================
Basic method:    True (Time: 0.000015 seconds)
Improved method: True (Time: 0.000008 seconds)
Advanced method: True (Time: 0.000003 seconds)

Checking if 1009 is prime using all methods:
==================================================
Basic method:    True (Time: 0.000156 seconds)
Improved method: True (Time: 0.000012 seconds)
Advanced method: True (Time: 0.000004 seconds)

Checking if 10007 is prime using all methods:
==================================================
Basic method:    Skipped (too slow)
Improved method: True (Time: 0.000038 seconds)
Advanced method: True (Time: 0.000008 seconds)

Checking if 100003 is prime using all methods:
==================================================
Basic method:    Skipped (too slow)
Improved method: True (Time: 0.000098 seconds)
Advanced method: True (Time: 0.000012 seconds)

How the Advanced Method Works

1. Pre-computed Small Primes

Python
if number in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]:
    return True

For small numbers, we already know the answer. This saves computation time.

2. Quick Divisibility Checks

Python
if number % 2 == 0 or number % 3 == 0 or number % 5 == 0:
    return False

We quickly eliminate numbers divisible by 2, 3, or 5.

3. 6k ± 1 Optimization

Python
for i in range(7, limit, 6):
    if number % i == 0 or number % (i + 4) == 0:
        return False

This uses a mathematical fact: all prime numbers greater than 3 can be written as 6k+1 or 6k-1. This lets us skip many numbers.

Performance Comparison

Here's how much faster each method is:

Method For Number 1009 For Number 100003 Speed Rating
Basic Method 0.000156 seconds Too slow Slow
Improved Method 0.000012 seconds 0.000098 seconds Fast
Advanced Method 0.000004 seconds 0.000012 seconds Very Fast

You can explore more about efficient programming with pattern printing in Python.

Interactive Prime Checker

Try checking if numbers are prime yourself! Enter any number and see the result instantly.

How to Use This Checker

  1. Type any positive number in the box above
  2. Click the "Check Prime" button
  3. See if your number is prime or not
  4. Try different numbers to understand the pattern

Try These Numbers

Here are some interesting numbers to test:

  • Small primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29
  • Large primes: 97, 101, 103, 107, 109, 113
  • Non-primes: 4, 6, 8, 9, 10, 12, 14, 15, 16, 18
  • Challenge: 1009, 1013, 1019, 1021

Performance Comparison

Let's see how our different methods perform with various sized numbers. This helps you choose the right method for your needs.

Time Complexity Analysis

Here's how the time complexity works for each method:

Method Time Complexity Space Complexity Best For
Basic Method O(n) O(1) Learning only
Improved Method O(√n) O(1) Medium numbers
Advanced Method O(√n) O(1) Large numbers

Real-World Performance Test

Performance Tester

Test how fast each method works with different sized numbers:

When to Use Each Method

Use Basic Method When:

  • You're learning programming
  • You need to understand the concept clearly
  • You're working with very small numbers (less than 100)

Use Improved Method When:

  • You're working with medium-sized numbers (100 to 100,000)
  • You want a good balance of simplicity and speed
  • You're building educational software

Use Advanced Method When:

  • You're working with large numbers (100,000+)
  • Performance is critical
  • You're building production software

Interactive Quiz

Test your understanding of prime numbers and the methods we learned!

Question 1: Which of these numbers is prime?

Question 2: Why is the square root method faster?

Question 3: What makes 2 special among prime numbers?

Question 4: For checking if 100 is prime, how many numbers does the improved method check?

Frequently Asked Questions

For very large numbers (millions of digits), mathematicians use advanced methods like the Miller-Rabin primality test or AKS primality test. For normal programming tasks, our advanced square root method works well for numbers up to several million.

By definition, a prime number must have exactly two distinct positive divisors: 1 and itself. The number 1 only has one divisor (itself), so it doesn't meet the requirement. This definition helps keep mathematical theorems simple and consistent.

No, by mathematical convention, prime numbers are defined only for positive integers greater than 1. Negative numbers are not considered prime, even if their absolute value would be prime.

As of 2024, the largest known prime number is 2^82,589,933 - 1, which has over 24 million digits! It was discovered as part of the Great Internet Mersenne Prime Search (GIMPS) project.

Prime numbers are crucial in computer security and cryptography. When you shop online or use banking apps, prime numbers help encrypt your data. They're also used in computer algorithms, random number generation, and hash functions.

For learning: use the basic method. For small numbers (under 1000): improved method is fine. For larger numbers or production code: use the advanced method. If you need to check many numbers, consider using libraries like sympy which have highly optimized implementations.

External Resources for Further Learning

About The Author

Leave a Reply

Your email address will not be published. Required fields are marked *

  • Rating
Did you find the information you were looking for on this page?

0 / 400