Prime Number Checker
Free, with no sign up. Calculations run on your device; your entries stay in this browser.
Enter a nonnegative integer from 0 to 3,299,999,999,999,999,999,999,999: strictly less than 3.3 × 10²⁴, at most 25 decimal digits, without separators or exponents. The number is unitless. Zero and one are neither prime nor composite. Every primality verdict within this range is deterministic; it is not a probable-prime result.
Your result
Write n − 1 = 2^s × d with d odd. For each base a, require a^d ≡ 1 (mod n), or a^(2^r × d) ≡ −1 (mod n) for some 0 ≤ r < s.
Primary source: Sorenson and Webster, Strong Pseudoprimes to Twelve Prime Bases (2015), Theorem 1.1.
The published deterministic witness set is the first 13 primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41. Sorenson and Webster establish the first composite passing all 13 at 3,317,044,064,679,887,385,961,981, which exceeds this page’s strict input bound. The first 12 bases alone are insufficient for the whole supported range. Full factorization is available for composites at most 10¹². For larger composites, only prime divisors at most 10,000 are searched; the first found is the smallest factor. If none is found, the result still says composite and explicitly marks factorization incomplete. A prime factors as itself.
Worked example
97 is prime. For 84, the full factorization is 2² × 3 × 7 and its smallest factor is 2. A composite may fail a Miller–Rabin witness even when no small factor is found.
How to use this tool
Enter your measured values and select Calculate to see the result, formula and details below.
Frequently asked questions
Is this a deterministic prime test?
Yes, within the stated strict bound below 3.3 × 10²⁴. It uses exact BigInt modular arithmetic and all 13 published prime witnesses through 41.
Why is there sometimes no factor?
Primality and factorization are different tasks. Composites up to 10¹² are fully factored; above that, the bounded search only checks prime factors up to 10,000.
Can I check zero or one?
Yes. Both are reported as neither prime nor composite, with no prime factorization.