Prime Number Checker (with factorization)
Enter a non-negative integer up to 10^18. The calculator tests primality with trial division (deterministic up to ~10^15 in reasonable time) and gives the prime factorization for composite numbers.
- Previous prime
- 89
- Next prime
- 101
How it works
What's a prime number
A prime is a natural number greater than 1 that has no positive divisors other than 1 and itself. The first few primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37. They're the 'atoms' of integer arithmetic โ every integer โฅ 2 can be uniquely written as a product of primes (Fundamental Theorem of Arithmetic).
1 is not prime by convention. 0 and negative numbers are not prime. 2 is the only even prime โ every other even number is divisible by 2 and so composite.
How the test works
We use trial division: check divisibility by 2, then 3, then 5, 7, 11, โฆ up to โn. If none divides cleanly, n is prime. We use the 6kยฑ1 optimization which checks only candidates of the form 6k+1 or 6kโ1 (since all primes > 3 are of this form), reducing test count by 2/3.
Trial division is fast for n up to ~10^15 (sub-second). Beyond that, advanced tests like Miller-Rabin (probabilistic) or AKS (deterministic) are needed. We cap at 10^18 to prevent the browser from freezing on extreme inputs.
Why primes matter
Cryptography: RSA encryption multiplies two ~1000-digit primes to produce a number that's hard to factor. The security relies on the difficulty of factorizing large numbers โ a challenge that's been studied for thousands of years.
Math education: prime factorization is foundational. Concepts like GCD, LCM, modular arithmetic, fractions, and number theory all build on prime factor structure.
Computer science: hash table sizes, random number generators, and many algorithms use primes for their distinctive divisibility properties.
Frequently asked questions
โบIs 1 prime?
No. 1 is a 'unit', not a prime. Primes have exactly two distinct positive divisors (1 and itself); 1 has only one.
โบIs 0 prime?
No. Primes are integers > 1.
โบIs 2 prime?
Yes โ 2 is the only even prime. All other even numbers have 2 as a divisor besides 1 and itself.
โบHow is the next prime found?
By incrementing from n+1 and testing primality at each step. There's always a prime within n ร ln(n) of any number, so this terminates quickly even for large inputs.
โบWhy is the maximum 10^18?
JavaScript BigInt handles larger, but trial division becomes slow. 10^18 is safe for sub-second checks of typical inputs. Beyond, use specialized tools like SymPy or Mathematica.
โบCan you check 1000-digit primes?
Not with this tool โ trial division is too slow at that scale. Cryptography uses Miller-Rabin probabilistic tests for 1024-bit primes (~300 digits).
โบWhat's a Mersenne prime?
A prime of the form 2^p โ 1. As of 2025, only 51 are known. The largest known prime (M82589933) is a Mersenne prime with ~25 million digits.
โบDoes the data leave my browser?
No. Calculation runs locally; nothing is sent to a server.
Related tools
Last updated: