How to Check If a Number Is Prime
From quick mental math tricks to efficient programming loops and exact computer proofs. Compare methods and copy ready-to-use code in 6 languages.
Interactive Method Race & Step Counter
Enter any whole number to compare 3 different checking methods side-by-side to see how many steps each one takes:
Copy-and-Paste Code: Fast 6k ± 1 Prime Test
def is_prime(n: int) -> bool:
"""Fast prime check using the 6k +/- 1 shortcut."""
if n < 2:
return False
if n in (2, 3):
return True
if n % 2 == 0 or n % 3 == 0:
return False
# Test candidate divisors up to the square root
d = 5
while d * d <= n:
if n % d == 0 or n % (d + 2) == 0:
return False
d += 6
return True Quick Mental Math Rules (2, 3, 5, 7, 11, 13)
Before running long divisions or code, quick mental rules can immediately catch small factors. Enter any number below to test each rule:
Why Every Prime Above 3 Sits Next to a Multiple of 6
If you group whole numbers by multiples of 6, every number takes one of six forms:
Watch Out: While all primes greater than 3 sit next to a multiple of 6, not every number next to a multiple of 6 is prime! Select an example to see why:
Why You Can Stop at the Square Root (√N)
Why don't you have to check all numbers up to N? Here is the simple reason:
Every time you find a factor of a number, it comes with a matching partner (like 4 × 9 = 36).
If both factors in a pair were bigger than the square root (√36 = 6), multiplying them together would give a number bigger than 36 (for example, 7 × 7 = 49).
Therefore, at least one factor in every pair must be smaller than or equal to the square root. If you don't find any factor up to the square root, no factors can exist at all!
The Exact 7-Base Test for Huge Numbers
While dividing by hand takes more and more time as numbers grow, computers can test even 18-digit numbers in a split second using 7 special test bases:
1. Pull all factors of 2 out of (n - 1).
2. Run a special clock-math calculation using each of the 7 test numbers (2, 3, 5, 7, 11, 13, 17).
3. If the number passes all 7 tests, it is 100% guaranteed prime with zero mistakes.
Comparing Prime Checking Methods
Choose the right method depending on whether you are working by hand or writing code:
| Method | Speed | Memory Needed | Best Used For |
|---|---|---|---|
| Testing Every Number | Slowest | None | Learning the basics |
| Testing Up to Square Root | Fast for small numbers | None | Numbers up to 1 trillion |
| Sieve of Eratosthenes | Very fast for ranges | Needs grid memory | Finding all primes in a range |
| 7-Base Test (Our Engine) | Instant (microseconds) | None | Any single number up to 18 quintillion |
Famous Numbers & Tricky Cases Table
Explore numbers that look prime, tricky false primes, and major milestones. Click any row to test it in the race tool above:
| Number | Smallest Factor | Formula | Description | Result | Action |
|---|---|---|---|---|---|
| 4 | 2 | 2² | Smallest Composite Number | Composite | |
| 9 | 3 | 3² | Smallest Odd Composite | Composite | |
| 25 | 5 | 6(4) + 1 | Square of 5 (fits 6k+1 but not prime) | Composite | |
| 35 | 5 | 6(6) - 1 | 5 × 7 (fits 6k-1 but not prime) | Composite | |
| 49 | 7 | 6(8) + 1 | Square of 7 | Composite | |
| 97 | 97 | 6(16) + 1 | Largest 2-Digit Prime | Proven Prime | |
| 343 | 7 | 7³ | Cube of 7 | Composite | |
| 561 | 3 | 3 × 11 × 17 | Tricky number that fools simple tests | Composite | |
| 104729 | 104729 | 6(17455) - 1 | 10,000th Prime | Proven Prime | |
| 1299709 | 1299709 | 6(216618) + 1 | 100,000th Prime | Proven Prime | |
| 1000000007 | 1000000007 | 6(166666668) - 1 | Popular Programming Challenge Prime | Proven Prime | |
| 2147483647 | 2147483647 | 2³¹ - 1 | Famous Mersenne Prime (Largest 32-bit integer) | Proven Prime |
Step-by-Step Examples
Four complete examples showing how to test numbers of different sizes:
Square Root Limit: The square root of 97 is about 9.8, so test primes up to 9 (2, 3, 5, 7).
Tests: 97 is odd (not div by 2); 9+7=16 (not div by 3); doesn't end in 0 or 5 (not div by 5); 97 ÷ 7 leaves a remainder of 6.
Conclusion: Since none of the primes up to 9 divide 97, 97 is 100% prime.
Testing 7: Drop the last digit (34), subtract twice that digit (2 × 3 = 6): 34 - 6 = 28.
Multiple of 7: 28 divides cleanly by 7 (7 × 4), so 343 must divide by 7.
Breakdown: 343 ÷ 7 = 49 = 7 × 7. Thus, 343 = 7 × 7 × 7.
Why It's Tricky: 561 fools simple power tests because it mimics prime behavior for many base numbers.
Finding Factors: Checking the digits shows 5 + 6 + 1 = 12, which divides cleanly by 3!
Breakdown: 561 = 3 × 187 = 3 × 11 × 17. The 7-base test catches it as composite immediately.
Size: This is 2³¹ - 1, the largest value in a standard 32-bit computer integer.
Testing by Hand: The square root is 46,340, requiring thousands of trial divisions.
Fast Computer Test: Using the 7-base test, a computer proves it is prime in 0.01 milliseconds.
Related Calculators & Tools
Frequently Asked Questions
What is the fastest way to check if a number is prime?
For standard whole numbers up to 18.4 quintillion (2^64), computers use the deterministic 7-base Miller-Rabin test. By checking 7 verified witness numbers (2, 325, 9375, 28178, 450775, 9780504, and 1795265022), it proves whether a number is prime in less than a millisecond with 100% certainty. For smaller numbers done by hand, dividing by primes up to the square root is the best approach.
Why do we only need to test numbers up to the square root?
Every composite number can be split into a pair of factors (like 36 = 4 × 9 or 6 × 6). If both factors were bigger than the square root (6 × 6 = 36), multiplying them together would give a result larger than 36. That means at least one factor in every pair must be less than or equal to the square root. If you don't find any factor up to that point, none can exist anywhere!
What is the 6k ± 1 shortcut for checking primes?
All prime numbers larger than 3 sit right next to a multiple of 6 (either 1 number before or 1 number after, such as 5, 7, 11, 13, 17, 19). Once you check that a number is not divisible by 2 or 3, you only have to test potential divisors sitting right next to multiples of 6. This cuts out two-thirds (66%) of all testing steps.
Is every number sitting next to a multiple of 6 a prime?
No. While all primes above 3 sit next to a multiple of 6, some non-prime (composite) numbers do too! For example, 25 is next to 24 (6 × 4 + 1), 35 is next to 36 (6 × 6 - 1), and 49 is next to 48 (6 × 8 + 1). Even though they fit the pattern, 25 = 5 × 5, 35 = 5 × 7, and 49 = 7 × 7, so you still have to test them.
Why are 0 and 1 not prime numbers?
A prime number must have exactly two distinct positive factors: 1 and itself. The number 1 only has one factor (itself), and 0 has infinitely many factors. Also, keeping 1 out of the prime family ensures that every number has a single, unique prime factorization (for example, 6 is uniquely 2 × 3; if 1 were prime, you could write 1 × 2 × 3, 1 × 1 × 2 × 3, forever).
What is the difference between a probable prime and a proven prime?
A probable prime is a number that passed quick computer tests and is almost certainly prime, but hasn't had every possibility checked with an absolute mathematical guarantee. A proven prime has passed a complete test that guarantees it is 100% prime with no chance of error.