2026-09-29 7 min

Prime Checker

Test any integer to 10,000,000 for primality with trial division to √n, smallest factor, and witness division.

Calculator

Prime Check Inputs

Integer (n) Help

Integer from 2 to 10,000,000

Results update live as you type

Status:97 is PRIME — clean to √n = 9

Verdict for 97

VerdictPrime

EvidenceNo divisor ≤ 9

Divisions run4

Factorization97

Results

Optimal

Verdict

Prime

Exactly two divisors

Smallest Factor

None — prime

First exact divisor found

Cofactor (n ÷ smallest)

—

Partner of the smallest factor

Trial Bound √n

No need to test past this

Divisions Performed

Candidates tested (2, 3, 6k±1)

Full Factorization

Complete prime product

Trial division to √n is a complete proof at this scale: a witness equation for composites, a clean certificate for primes.

Visualizations

Trial-division workload

4tests run

9√n bound

Search depth used

tests / √n44%

Smallest factor vs n

smallest0

Formula

Divide by 2, 3, then 6k±1 candidates. The first exact hit witnesses compositeness; a clean run to √n certifies primality.

n is prime ⟺ no divisor d with 2 ≤ d ≤ √n

Alternative Form

n composite ⟹ witness: n = s × (n/s) with s = smallest factor

Variables

Symbol	Name	Unit	Description
n	Input integer	integer	2 to 10,000,000
√n	Trial bound	integer	Testing stops here (floored)
s	Smallest factor	integer	First exact divisor, if any
tests	Divisions run	count	Candidates actually tested

Explanation

Divisor pairs straddle √n, so scanning to the root covers every pair. Skipping multiples of 2 and 3 keeps the scan lean without missing candidates.

Derivation

If n = a·b with a ≤ b, then a ≤ √n. Hence testing all d ≤ √n finds a factor iff one exists; 6k±1 covers every prime above 3.

Step-by-Step Calculation

Follow each step to understand how the result is calculated from your inputs.

Step 1

Validate the input and compute the search bound.

bound = floor(√n)

n:97

bound:9

Result: Testing 97 against divisors ≤ 9

Step 2

Test the even tile first.

n mod 2

n mod 2:1

Intermediate: Remainder 1 — not even

Result: Odd: continue to 3

Step 3

Test 3, then stride 6k±1 past all multiples of 2 and 3.

Test 5, 7, 11, 13, 17, 19, …

candidates:4

Intermediate: 4 divisions performed

Result: No hit in 4 tests

Step 4

Stop at the first exact divisor — or at √n for primes.

Stop when d² > n or n mod d = 0

bound:9

Result: Certificate: nothing divides 97 below 9

Step 5

Factorize fully to corroborate the verdict.

n = Π p^e

Factorization:97

Result: 97 = 97

Step 6

Issue the final verdict with its evidence.

Prime ⟺ smallest = none

verdict:Prime

Result: 97 is prime (4 clean tests)

Final Answer

Prime

Worked Examples

See how the calculator works with different scenarios.

Scenario

Default prime suspect.

Inputs

n:97

Calculation

√97 ≈ 9.8 Test 2,3,5,7 — all leave remainders

Result

97 is prime

Interpretation

Four clean divisions to the bound certify primality.

Understanding Your Result

Your Result: Prime or composite with witness evidence — see the verdict card.

Typical range: Tests run from 1 (even n) up to ~2,000 rows for near-cap primes.

What This Means

Prime means exactly two divisors; composite comes with the smallest factor and its cofactor as proof.

Why It Matters

Primality gates cryptography, hashing, and fraction work — a wrong verdict corrupts everything downstream.

Professional Interpretation

A witness equation is a complete compositeness proof; a clean run to √n is a complete primality proof at this scale.

Recommendations

•Quote the witness for composites
•Cite the √n bound for primes
•Recheck evens above 2 instantly
•Reject 1 as neither
•Escalate huge candidates to probabilistic tests

Educational Content

Introduction

Primality asks whether an integer splits. Trial division answers exactly by testing every possible splitter up to the square root.

Concept Explanation

Divisors pair across √n, so the root bounds the search; the 6k±1 stride skips numbers already ruled out by 2 and 3.

Applications

▸Pre-screening cipher candidates

▸Hash-size prime selection

▸Fraction and GCD sanity checks

▸Contest primality questions

▸Factor-table building

▸Mental-math training

Benefits

•Exact verdict, not heuristic
•Witness equation for composites
•Certificate bound for primes
•Visible trial tiles
•Full factorization included

Limitations

•Caps at 10,000,000
•Linear scan slows near the cap
•Single number per run

Best Practices

•Test 2 first mentally
•Bound every search at √n
•Keep the witness equation
•Treat 1 as neither
•Stay within the cap

Common Misconceptions

Myth: You must test every number to n.

Truth: √n suffices — pairs cover the rest.

Myth: Odd numbers are usually prime.

Truth: 9, 15, 21, 25… odd composites are everywhere; only testing tells.

Myth: Large-looking numbers are prime.

Truth: 91 and 119 look prime but split (7×13, 7×17) — appearance proves nothing.

Myth: 1 is prime.

Truth: Primes need exactly two divisors; 1 has one.

Practical Tips

•Test 2 first — evens above 2 fall instantly
•Bound every manual check at √n
•Read the witness as the compositeness proof
•Use the 6k±1 stride (5, 7, 11, 13, …)
•Treat a clean run to √n as a certificate
•Reject 1 without testing
•Stay at or below 10,000,000

Common Mistakes

Testing past √n

Pairs already cover larger candidates — stop at the floored root.

Forgetting that 1 is neither

Primality verdicts need two divisors minimum; 1 cannot qualify.

Calling 91 prime

Run the 6k±1 stride: 91 = 7 × 13 exposes it.

Testing every integer instead of 6k±1

Skip multiples of 2 and 3 — every prime above 3 sits on the stride.

Accepting even numbers above 2

Any even n > 2 has factor 2; the first tile already decides.

Assumptions

This calculator makes the following assumptions to provide estimates:

Positive integers: Inputs are integers n with 2 ≤ n ≤ 10,000,000.

6k±1 stride: After 2 and 3, candidates follow 5, 7, 11, 13, ….

Exact remainders: Integer modulo decides every tile.

Early exit: The scan stops at the first exact divisor.

Local compute: Everything runs in the browser; nothing is uploaded.

Limitations

Be aware of these limitations when using this calculator:

10M cap: Larger candidates are rejected for responsiveness.

Scan cost: Near-cap primes test the most candidates.

No certificates: Primality proofs for huge n need Miller–Rabin, not trials.

Single candidate: One n per run; sieves enumerate ranges instead.

Frequently Asked Questions

Answers to common questions about this calculator.

How do you check if a number is prime?

Test divisibility by 2, 3, then 6k±1 candidates up to √n. No exact divisor means prime — this tool runs that gauntlet and shows every tile.

Why stop at the square root?

Divisors pair as d × (n/d); if none appears by √n, the partner search is exhausted too. For 97, testing to 9 settles it.

What is the smallest factor telling me?

The first exact divisor found — the entry point of the factorization. For 91 it is 7, exposing 91 = 7 × 13.

Is 1 prime?

No. 1 has exactly one divisor, so it is neither prime nor composite — the checker rejects it with that explanation.

Is 2 prime?

Yes — the only even prime. Its only divisors are 1 and itself.

Why is the cap 10,000,000?

Trial division scans toward √n, so worst-case primes near the cap test ~2,000 candidates — interactive, but unbounded inputs would freeze the page.

What is a witness division?

One exact equation proving compositeness, e.g. 91 = 7 × 13. Primes instead get a no-divisor certificate up to √n.

Can an even number above 2 be prime?

Never — every even number above 2 is divisible by 2. The checker flags that on the very first tile.

How does this differ from the nth-prime tool?

This answers "is THIS number prime?" with a witness; the prime-number tool answers "what is the kth prime?" with a sieve.

Related Calculators

Explore more calculators related to this topic.

Related Guides

Deepen your understanding with these educational resources.

Trial division without missing 7

The 6k±1 stride order.

Witness equations that convince

Writing compositeness proofs.

Why √n is enough

Divisor pairing, visualized.

The 91 trap and friends

Composites that look prime.

Glossary

Technical terms used in mortgage calculations explained in plain language.

Prime number: Integer above 1 with exactly two divisors.
Composite number: Integer above 1 that splits into smaller factors.
Trial division: Testing divisors ascending from 2.
Witness: An exact factorization proving compositeness.
Smallest prime factor: The least prime dividing n.
Cofactor: n divided by the smallest factor.
6k±1 stride: Candidate pattern covering all primes above 3.
Square-root bound: Testing ceiling from divisor pairing.

Authoritative References

Trusted sources and standards referenced by this calculator.

Wikipedia — Primality test Wikipedia — Trial division Wikipedia — Prime number MathWorld — Prime Number Math is Fun — Prime Numbers Khan Academy — Prime numbers The Prime Pages (UTM)

Applicable Standards

Common Core 4.OA.B.4 — prime and composite numbersNCTM Number and Operations — factors and multiples

Was This Calculator Helpful?

Report Issue

Page Information

Last Updated:

2026-09-29

Version:

2.0.0

References:

License:

Free to use for educational and professional purposes.