Prime Number Checker & Factorizer
Check primality, factorize and list primes up to N.
Overview
The Prime Number Checker and Factorizer answers three questions in one place: is N prime, what are N's prime factors, and which primes lie at or below N? It handles small to medium integers exactly and uses arbitrary-precision arithmetic so large inputs don't overflow.
It is useful for number-theory students working through Euclid's theorems, cryptography learners exploring how RSA's hardness depends on factoring, contest programmers and code-katas players who need a quick gut check on primality.
How it works
Primality testing uses trial division by small primes up to sqrt(N). For very large inputs, Miller-Rabin with deterministic witnesses certifies primality for N up to several quintillion exactly, and probabilistically for larger ones.
Factorisation peels off small prime factors by trial division, then switches to Pollard's rho for larger composites. The list of primes up to N uses the Sieve of Eratosthenes, which marks multiples of each prime as composite in linear-log time.
Examples
Is 97 prime? → Yes
Factor 360 → 2^3 * 3^2 * 5
Primes up to 30 → 2, 3, 5, 7, 11, 13, 17, 19, 23, 29
Factor 1729 → 7 * 13 * 19 (Ramanujan-Hardy number)
FAQ
Is 1 prime?
No. Modern definition restricts primes to integers greater than 1 with exactly two divisors.
How big can N be?
For exact factorisation, anything up to about 10^18 finishes quickly. Larger numbers can take noticeably longer depending on factor structure.
Why is factoring hard for big numbers?
The fastest known classical algorithms run in subexponential time. That's the foundation of RSA security — keys are products of two very large primes.
Are twin primes shown?
The Sieve view orders primes in ascending order, so twin primes (pairs differing by 2 like 11, 13) appear consecutively.
Is there a formula for primes?
No simple formula generates exactly the primes. The Prime Number Theorem says there are roughly N / ln(N) primes up to N, but the spacing of individual primes is irregular.