Methods, Explanations & Code

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:

Quick Examples:
Method 1 Standard Division Tests every odd number up to √N
Steps Taken: 323 steps
Time: 0.08 ms
Method 2 (Optimized) 6k ± 1 Shortcut Skips multiples of 2 and 3
Steps Taken: 108 steps (3× faster)
Time: 0.03 ms
Method 3 (Fastest) Exact 7-Base Check Tests 7 key numbers directly
Steps Taken: 7 base rounds
Time: 0.01 ms (Instant)
Result: 104,729 is a Prime Number

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
01

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:

02

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:

• Multiples of 6 (6, 12, 18, 24...) are divisible by 2 and 3.
• 2 after a multiple of 6 (8, 14, 20...) is always even (divisible by 2).
• 3 after a multiple of 6 (9, 15, 21...) is always divisible by 3.
• 4 after a multiple of 6 (10, 16, 22...) is always even (divisible by 2).
• Only 1 before or 1 after (6k - 1 or 6k + 1) can possibly be prime!

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:

Number: 25 – Form: 6(4) + 1
Status: Not Prime! It equals 5 × 5.
This shows that fitting the pattern is a helpful clue, but you still need to test for factors.
Modulo 6 integer wheel isolating 6k-1 and 6k+1 spoke lanes for prime candidates
The Modulo-6 Prime Wheel (6k ± 1) Only integers on the +1 and -1 spokes avoid multiples of 2 and 3, slashing trial division candidates by two-thirds.
03

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:

The Factor Pair Balance:

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!

Inspect Factor Pairs for N =
Geometric rectangle factor pair diagram proving one factor is always less than or equal to square root N
Square-Root Factor Symmetry Geometry As factor a grows past sqrt(N), its partner factor b drops below sqrt(N) — so checking above sqrt(N) is never needed.
04

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:

The 7 Key Bases: {2, 3, 5, 7, 11, 13, 17} (100% exact for all numbers up to 18 quintillion)
How It Works in Simple Steps:

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.

Comparison showing how 7 verified Miller-Rabin bases eliminate every pseudoprime up to 2^64
Verified Base Coverage up to 2^64 While single bases can be fooled by pseudoprimes, checking the exact 7-base witness set proves primality cleanly.
05

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
06

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
07

Step-by-Step Examples

Four complete examples showing how to test numbers of different sizes:

Example 1: Testing 97 Verdict: Prime

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.

Example 2: Testing 343 Verdict: Composite

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.

Example 3: Testing 561 (The Trick Number) Verdict: Tricky Composite

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.

Example 4: Testing 2,147,483,647 Verdict: Huge Prime

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.