Primality Checker

The primality checker tells you whether an integer is prime, and — unlike most calculators online — shows you the actual algorithm that proved it, not a cached lookup table. Type any integer, positive or negative, small or enormous, and the tool decides which real algorithm to run based on its size.

For numbers under 10¹² (one trillion), it runs genuine trial division: starting at 2, it tries every integer candidate up to the floor of √n as a possible divisor, stopping the moment one divides evenly (composite) or confirming none does once every candidate up to √n has been checked (prime). For huge candidate counts the trace shown is capped to the first ~18 tried plus the final one, with an honest note about how many were skipped in the display — but every single candidate is still actually checked by the code, none are skipped in the computation.

For numbers at or above that threshold — the size range used in cryptography — trial division would take too long, so the tool switches to the Miller–Rabin primality test with a fixed, deterministic set of 13 prime witnesses (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41). This exact witness set is a well-known result: it has no false positives for any n below 3,317,044,064,679,887,385,961,981 (about 3.3×10²⁴), a bound established by computational verification (see Sorenson & Webster, 2015, and the widely reproduced deterministic-witness table it belongs to). Above that bound the same test still runs, but the tool tells you honestly that the guarantee becomes an extremely strong probabilistic one rather than a mathematical certainty.

The Miller–Rabin trace writes n − 1 = 2ˢ × d with d odd, then walks through real BigInt modular exponentiation — square-and-multiply, reducing modulo n at every single step so the numbers never explode — bit by bit for the first witness, and reports each witness's verdict, including which witness proves compositeness if the number turns out not to be prime. Everything runs locally in your browser: no server, no external API, no data ever leaves your device.