Table of Contents
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:

The Rule for Prime Numbers
Here’s the simple rule to remember:
- A prime number must be greater than 1
- It can only be divided evenly by 1 and itself
- 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.
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:
- Quick Check: Is 13 ≥ 2? Yes! ✓
- Test 2: 13 ÷ 2 = 6 remainder 1 (not divisible) ✓
- Test 3: 13 ÷ 3 = 4 remainder 1 (not divisible) ✓
- Test 4: 13 ÷ 4 = 3 remainder 1 (not divisible) ✓
- Test 5: 13 ÷ 5 = 2 remainder 3 (not divisible) ✓
- Test 6: 13 ÷ 6 = 2 remainder 1 (not divisible) ✓
- Test 7: 13 ÷ 7 = 1 remainder 6 (not divisible) ✓
- Test 8: 13 ÷ 8 = 1 remainder 5 (not divisible) ✓
- Test 9: 13 ÷ 9 = 1 remainder 4 (not divisible) ✓
- Test 10: 13 ÷ 10 = 1 remainder 3 (not divisible) ✓
- Test 11: 13 ÷ 11 = 1 remainder 2 (not divisible) ✓
- 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:
- Quick Check: Is 12 ≥ 2? Yes! ✓
- 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
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
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
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
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
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:

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
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
import math
We import the math module to use the sqrt()
function for square root calculation.
2. Handle Special Cases
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
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:

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
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
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
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
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
- Type any positive number in the box above
- Click the "Check Prime" button
- See if your number is prime or not
- 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
- Official Python Documentation - Complete reference for Python programming
- Prime Numbers on Wikipedia - Mathematical background and history
- GeeksforGeeks Prime Number Tutorial - Additional programming examples
Leave a Reply