Prime Number Calculator: Finally Understand Prime Numbers
Let me tell you about the first time I needed to check if a number was prime. I was in 7th grade, and my teacher asked, "Is 7919 prime?" I had no idea. I started dividing by every number up to 7919—which took forever.
Then I learned the trick: you only need to check up to the square root. And once you understand the 6k ± 1 pattern, checking primes becomes surprisingly efficient.
In this guide, I'll walk you through everything you need to know about prime numbers—from basic primality testing to prime factorization, divisor analysis, and finding nearest primes.
Ready to master prime numbers? Try our Prime Number Calculator and watch each calculation unfold step by step.
What Is a Prime Number?
A prime number is a natural number greater than 1 that has exactly two divisors: 1 and itself.
Simple Examples
| Number | Divisors | Prime? |
|---|---|---|
| 2 | 1, 2 | ✓ (smallest prime) |
| 3 | 1, 3 | ✓ |
| 4 | 1, 2, 4 | ✗ (composite) |
| 5 | 1, 5 | ✓ |
| 6 | 1, 2, 3, 6 | ✗ (composite) |
| 7 | 1, 7 | ✓ |
| 11 | 1, 11 | ✓ |
Key Properties
- 2 is the only even prime number
- All other primes are odd (and end in 1, 3, 7, or 9)
- Prime numbers are infinite (proved by Euclid ~300 BCE)
- Every composite number has a prime factor ≤ √n
Why Prime Numbers Matter
| Field | Why Primes? |
|---|---|
| Cryptography | RSA encryption uses huge primes (600+ digits) |
| Number Theory | Fundamental Theorem of Arithmetic: every number is a unique product of primes |
| Computer Science | Hashing, random number generation, error detection |
| Mathematics | Goldbach's conjecture, twin primes, prime gaps |
| Everyday Life | Gear ratios, musical intervals, scheduling |
How to Check If a Number Is Prime: 3 Methods
Method 1: Trial Division (Best for understanding)
For number n, test divisibility by all integers from 2 to √n.
Example: Check if 7919 is prime
| Step | Divisor | Calculation | Result |
|---|---|---|---|
| 1 | 2 | 7919 ÷ 2 = 3959.5 | Not integer |
| 2 | 3 | 7+9+1+9=26, not divisible by 3 | Not integer |
| 3 | 5 | Last digit not 0 or 5 | Not integer |
| 4 | 7 | 7 × 1131 = 7917, remainder 2 | No |
| 5 | 11 | 11 × 720 = 7920, remainder -1 | No |
| ... | ... | ... | ... |
| √7919 ≈ 89 | Check up to 89 | No divisors found | Prime! |
Method 2: 6k ± 1 Optimization
All primes greater than 3 can be written as 6k ± 1 (i.e., 1 less or 1 more than a multiple of 6).
Pattern: 5, 7, 11, 13, 17, 19, 23, 25(no), 29, 31...
Why this works:
- Numbers of form 6k (divisible by 6) → composite
- Numbers of form 6k + 2 (even) → composite
- Numbers of form 6k + 3 (divisible by 3) → composite
- Numbers of form 6k + 4 (even) → composite
- Only 6k ± 1 remain for primality testing
Method 3: Sieve of Eratosthenes (For finding many primes)
To find all primes up to N:
- List numbers 2 to N
- Mark multiples of 2 (except 2)
- Mark multiples of 3 (except 3)
- Continue up to √N
- Unmarked numbers are prime
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
Prime Composite Prime Composite Prime Composite ...
The Primality Testing Algorithm
Our calculator uses an optimized trial division algorithm:
Step 1: Basic Validation
if n < 2 → not prime
if n === 2 → prime
Step 2: Quick Divisibility Tests
if n % 2 === 0 → not prime (unless n === 2)
if n % 3 === 0 → not prime (unless n === 3)
if n % 5 === 0 → not prime (unless n === 5)
Step 3: 6k ± 1 Scanning
for i = 5; i <= √n; i += 6:
if n % i === 0 or n % (i+2) === 0:
return composite
return prime
Complexity
| Number Size | Operations | Time (approx) |
|---|---|---|
| 1,000 | ~30 | < 1ms |
| 1,000,000 | ~1,000 | ~1ms |
| 100,000,000 | ~10,000 | ~10ms |
| 1,000,000,000 | ~31,000 | ~50ms |
Prime Factorization
Every composite number can be uniquely expressed as a product of primes.
Factorization Tree Method
Example: 84
84
/ \
4 21
/ \ / \
2 2 3 7
84 = 2² × 3 × 7
Step-by-Step Factorization
For n = 84:
- Divide by 2: 84 ÷ 2 = 42 (factor: 2)
- Divide by 2: 42 ÷ 2 = 21 (factor: 2)
- 21 ÷ 3 = 7 (factor: 3)
- 7 is prime (factor: 7)
Result: 2² × 3 × 7
Examples
| Number | Prime Factorization |
|---|---|
| 12 | 2² × 3 |
| 18 | 2 × 3² |
| 30 | 2 × 3 × 5 |
| 36 | 2² × 3² |
| 48 | 2⁴ × 3 |
| 60 | 2² × 3 × 5 |
| 100 | 2² × 5² |
| 256 | 2⁸ |
| 7919 | 7919 (prime) |
Divisors and Divisor Pairs
Finding All Divisors
For any number n, divisors come in pairs: if a divides n, then n/a also divides n.
Example: Divisors of 36
| Pair | Multiplication |
|---|---|
| 1 × 36 | = 36 |
| 2 × 18 | = 36 |
| 3 × 12 | = 36 |
| 4 × 9 | = 36 |
| 6 × 6 | = 36 |
All divisors: 1, 2, 3, 4, 6, 9, 12, 18, 36 (9 divisors)
Divisor Count Formula (Tau Function)
If n = p₁ᵉ¹ × p₂ᵉ² × ... × pₖᵉᵏ
Then τ(n) = (e₁ + 1)(e₂ + 1)...(eₖ + 1)
Example: 36 = 2² × 3²
- τ(36) = (2+1)(2+1) = 3 × 3 = 9 ✓
Divisor Sum Formula (Sigma Function)
σ(n) = ∏(pᵢ^(eᵢ+1) - 1)/(pᵢ - 1)
Example: 36
- σ(36) = (2³ - 1)/(2-1) × (3³ - 1)/(3-1) = 7/1 × 26/2 = 7 × 13 = 91
- Check: 1+2+3+4+6+9+12+18+36 = 91 ✓
Prime Neighbors
Previous Prime
The largest prime less than n.
| Number | Previous Prime |
|---|---|
| 10 | 7 |
| 20 | 19 |
| 50 | 47 |
| 100 | 97 |
| 1000 | 997 |
Next Prime
The smallest prime greater than n.
| Number | Next Prime |
|---|---|
| 10 | 11 |
| 20 | 23 |
| 50 | 53 |
| 100 | 101 |
| 1000 | 1009 |
Prime Gaps
The difference between consecutive primes.
| Gap | Primes |
|---|---|
| 1 | 2, 3 |
| 2 | 3, 5 (twin primes) |
| 4 | 7, 11 |
| 6 | 23, 29 |
| 8 | 89, 97 |
Special Types of Primes
| Type | Definition | Examples |
|---|---|---|
| Twin primes | Differ by 2 | (3,5), (11,13), (17,19) |
| Cousin primes | Differ by 4 | (3,7), (7,11), (13,17) |
| Sexy primes | Differ by 6 | (5,11), (7,13), (11,17) |
| Mersenne primes | 2ⁿ - 1 | 3, 7, 31, 127, 8191 |
| Fermat primes | 2^(2ⁿ) + 1 | 3, 5, 17, 257, 65537 |
| Sophie Germain | p and 2p+1 both prime | 2, 3, 5, 11, 23 |
| Safe primes | (p-1)/2 is prime | 5, 7, 11, 23, 47 |
How to Use Our Prime Calculator
Step 1: Enter a Number
Type any positive integer (up to 1 billion). Example: 7919
Step 2: Click Analyze
The calculator performs:
- Basic validation
- Quick divisibility tests (2, 3, 5)
- Full divisibility scan up to √n
Step 3: Explore Results
You'll see three tabs:
Analysis Tab:
- Prime/composite classification
- Square root
- Total divisor count
- Previous and next prime
Factors Tab:
- Prime factorization with exponent notation
- All divisors (complete list)
- Divisor pairs
- Factorization tree visualization
Steps Tab:
- Step-by-step primality test
- Each check explained
- Pass/fail indicators
Step-by-Step Examples
Example 1: 7919 (Prime Number)
Step 1: Basic Validation
- n = 7919 ≥ 2 ✓
- Not 2
- √7919 ≈ 89
Step 2: Quick Divisibility Tests
- Divisible by 2? No (odd)
- Divisible by 3? 7+9+1+9=26, not divisible by 3
- Divisible by 5? Last digit not 0 or 5
Step 3: Full Divisibility Scan
- Check divisors from 7 to 89 (6k ± 1 pattern)
- Numbers checked: 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89
- No divisors found
Result: 7919 is PRIME
- Divisors: 1, 7919
- Next prime: 7927
- Previous prime: 7919? Actually previous is 7919 itself (or 7883 if searching before)
Example 2: 10007 (Prime Number)
Step 1: 10007 ≥ 2 ✓ Step 2: Not divisible by 2, 3, or 5 Step 3: √10007 ≈ 100. Check primes up to 97
- 10007 ÷ 7 = 1429.57
- 10007 ÷ 11 = 909.73
- 10007 ÷ 13 = 769.77
- 10007 ÷ 17 = 588.65
- ...
- 10007 ÷ 97 = 103.16
- No divisors found
Result: 10007 is PRIME
Example 3: 99991 (Prime Number)
Known prime! √99991 ≈ 316. Check up to 313.
- No divisors found → Prime
Example 4: 104729 (Prime Number)
The 10,000th prime! √104729 ≈ 323.
Example 5: 2147483647 (Mersenne Prime)
2³¹ - 1 = 2,147,483,647 — a famous Mersenne prime discovered by Euler in 1772.
Example 6: 100 (Composite Number)
Step 1: 100 ≥ 2 ✓ Step 2: Divisible by 2? Yes (even) → Composite
Prime Factorization:
- 100 ÷ 2 = 50
- 50 ÷ 2 = 25
- 25 ÷ 5 = 5
- 5 is prime
Result: 100 = 2² × 5²
- Divisors: 1, 2, 4, 5, 10, 20, 25, 50, 100 (9 divisors)
- Next prime: 101
- Previous prime: 97
Common Mistakes
Mistake 1: Thinking 1 Is Prime
Wrong: "1 is prime because it has no factors" Right: 1 has only one factor (itself), not two. Prime numbers must have exactly two distinct factors.
Mistake 2: Thinking 2 Is Composite
Wrong: "2 is even, so it must be composite" Right: 2 is the only even prime. It has exactly two factors: 1 and 2.
Mistake 3: Checking Too Many Divisors
Wrong: Testing divisibility up to n instead of √n Right: If a divisor exists, its partner is ≥ √n. You only need to check up to √n.
Mistake 4: Forgetting the 6k ± 1 Pattern
Wrong: Testing every odd number (3, 5, 7, 9, 11, 13...) Right: After checking 2 and 3, only test numbers of form 6k ± 1.
Mistake 5: Confusing Prime with Coprime
Wrong: "7 and 9 are both prime" Right: 9 is composite, but 7 and 9 are coprime (share no common factors)
Mistake 6: Thinking All Odd Numbers Are Prime
Wrong: "9, 15, 21, 25 are prime" Right: These are composite: 9=3×3, 15=3×5, 21=3×7, 25=5×5
Quick Reference: First 100 Primes
| # | Prime | # | Prime | # | Prime | # | Prime |
|---|---|---|---|---|---|---|---|
| 1 | 2 | 26 | 101 | 51 | 233 | 76 | 383 |
| 2 | 3 | 27 | 103 | 52 | 239 | 77 | 389 |
| 3 | 5 | 28 | 107 | 53 | 241 | 78 | 397 |
| 4 | 7 | 29 | 109 | 54 | 251 | 79 | 401 |
| 5 | 11 | 30 | 113 | 55 | 257 | 80 | 409 |
| 6 | 13 | 31 | 127 | 56 | 263 | 81 | 419 |
| 7 | 17 | 32 | 131 | 57 | 269 | 82 | 421 |
| 8 | 19 | 33 | 137 | 58 | 271 | 83 | 431 |
| 9 | 23 | 34 | 139 | 59 | 277 | 84 | 433 |
| 10 | 29 | 35 | 149 | 60 | 281 | 85 | 439 |
| 11 | 31 | 36 | 151 | 61 | 283 | 86 | 443 |
| 12 | 37 | 37 | 157 | 62 | 293 | 87 | 449 |
| 13 | 41 | 38 | 163 | 63 | 307 | 88 | 457 |
| 14 | 43 | 39 | 167 | 64 | 311 | 89 | 461 |
| 15 | 47 | 40 | 173 | 65 | 313 | 90 | 463 |
| 16 | 53 | 41 | 179 | 66 | 317 | 91 | 467 |
| 17 | 59 | 42 | 181 | 67 | 331 | 92 | 479 |
| 18 | 61 | 43 | 191 | 68 | 337 | 93 | 487 |
| 19 | 67 | 44 | 193 | 69 | 347 | 94 | 491 |
| 20 | 71 | 45 | 197 | 70 | 349 | 95 | 499 |
| 21 | 73 | 46 | 199 | 71 | 353 | 96 | 503 |
| 22 | 79 | 47 | 211 | 72 | 359 | 97 | 509 |
| 23 | 83 | 48 | 223 | 73 | 367 | 98 | 521 |
| 24 | 89 | 49 | 227 | 74 | 373 | 99 | 523 |
| 25 | 97 | 50 | 229 | 75 | 379 | 100 | 541 |
Prime Number Theorem
The Prime Number Theorem describes how primes are distributed:
π(x) ~ x / ln(x)
Where π(x) is the number of primes ≤ x.
| x | π(x) (actual) | x/ln(x) (approx) | Ratio |
|---|---|---|---|
| 10 | 4 | 4.3 | 0.93 |
| 100 | 25 | 21.7 | 1.15 |
| 1,000 | 168 | 144.8 | 1.16 |
| 10,000 | 1,229 | 1,085.7 | 1.13 |
| 100,000 | 9,592 | 8,685.9 | 1.10 |
| 1,000,000 | 78,498 | 72,382.4 | 1.08 |
Frequently Asked Questions
What's the largest known prime?
As of 2024, the largest known prime is 2⁸²⁵⁸⁹⁹³³ - 1 (a Mersenne prime with over 24 million digits).
How many primes are there?
Infinite! Euclid proved this around 300 BCE.
What's the smallest prime?
2 (not 1).
Is 1 prime?
No. By definition, primes have exactly two distinct positive divisors. 1 has only one.
Is 0 prime?
No. Primes are defined for natural numbers greater than 1.
What's a composite number?
A natural number > 1 that is not prime (has more than 2 divisors).
How fast is your calculator?
It checks numbers up to 1 billion in under 100ms using optimized trial division.
Why does the calculator show "Previous Prime" as None for 2?
Because there's no prime less than 2.
What are twin primes?
Pairs of primes that differ by 2, like (3,5), (11,13), (17,19).
Can prime numbers be negative?
In standard number theory, primes are positive. Some contexts include negative primes, but our calculator only handles positive integers.
Your Turn: Start Exploring
Prime numbers used to seem mysterious to me. Now I understand they're the building blocks of all numbers—the "atoms" of arithmetic.
Here's your practice plan:
- Start with small numbers: Check 2, 3, 4, 5, 6, 7
- Try perfect squares: 4, 9, 16, 25, 36 (all composite)
- Test famous primes: 7919, 10007, 99991, 104729
- Explore Mersenne primes: 3, 7, 31, 127, 8191
- Find neighbors: Pick a number, find previous/next prime
- Factor composites: Break down 100, 144, 256, 512
- Study the steps: Understand each check
Ready to start? Open up our Prime Number Calculator and try it yourself. Start with 7919, then try 10007, then 99991.
You'll discover the beauty of prime numbers faster than you think.
Have questions? Stuck on a particular number? Drop a comment below or reach out. I've been where you are, and I'm happy to help.
— The Solvezi Team
Disclaimer: This calculator is for educational purposes. While we aim for accuracy, extremely large numbers (>1 billion) may be slow to compute.
