Prime Number Tester

Test if a number is prime, find the next or previous prime, or factorize any number. Supports very large numbers via BigInt and Miller-Rabin.

Enter a number and click Test
Enter a number above and press Test to check primality.

How to Use the Prime Number Tester

  1. Test mode — type any integer (no limit on size) and click Test. The result shows prime/composite, the number of digits, and the nearest primes.
  2. Previous/Next Prime — click the arrow buttons to jump to the nearest prime above or below your number.
  3. Generate mode — set a count and generate the first N prime numbers as a list you can copy.
  4. Factorize mode — decompose a number into its prime factors, shown as individual chips and as a mathematical expression.

What Makes a Number Prime?

A prime number is a natural number greater than 1 with exactly two divisors: 1 and itself. The number 1 is not prime by convention (it has only one divisor). The number 2 is the only even prime — every other even number is divisible by 2. Prime numbers become less frequent as numbers grow larger, following the prime number theorem: the number of primes up to N is approximately N / ln(N).

Trial Division Algorithm

For numbers with fewer than 15 digits, this tool uses trial division: it checks divisibility by every integer from 2 up to the square root of the candidate. If no divisor is found, the number is prime. The square root limit is the key optimization — if n has a factor greater than √n, then it must also have a factor less than √n (because the factors come in pairs that multiply to n). Additional optimizations: skip even numbers after checking 2, and only test numbers of the form 6k ± 1 since all primes greater than 3 have this form.

Miller-Rabin Primality Test

For large numbers (15+ digits), trial division becomes too slow. This tool uses the deterministic Miller-Rabin test with a specific set of witnesses that is provably correct for all numbers below 3.3 × 10²⁴. For numbers beyond that range, it uses a large set of witnesses to achieve a false-positive probability below 2⁻⁶⁴. The algorithm works by writing n − 1 as 2ˢ × d (factoring out powers of 2), then checking if modular exponentiation witnesses confirm or contradict primality.

Applications of Prime Numbers

Prime numbers are the foundation of modern cryptography. RSA encryption relies on the difficulty of factoring the product of two large primes. A 2048-bit RSA key uses primes with about 617 decimal digits — numbers that would take thousands of years to factor with current computers and algorithms. Diffie-Hellman key exchange and elliptic curve cryptography also depend on prime moduli. In mathematics, prime numbers appear in the Riemann hypothesis, one of the seven Millennium Prize Problems with a $1 million reward for a proof or disproof.

Interesting Prime Facts

There are infinitely many primes (proved by Euclid around 300 BC). The largest known prime as of 2024 is 2¹³⁶²⁷⁹⁸⁴¹ − 1, a Mersenne prime with 41,024,320 digits. Twin primes (primes differing by 2, like 11 and 13) are conjectured to be infinite but this remains unproven. Sophie Germain primes (p where 2p + 1 is also prime) are used in some cryptographic protocols. The prime gaps (distances between consecutive primes) grow on average as log(n) but can be arbitrarily large.

Frequently Asked Questions

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. Examples: 2, 3, 5, 7, 11, 13... The number 1 is not prime by definition. 2 is the only even prime.
Trial division checks divisibility by every integer from 2 up to the square root of the candidate. If no divisor is found, the number is prime. The square root limit works because any composite number n must have at least one factor at or below √n.
Miller-Rabin is a probabilistic primality test much faster than trial division for large numbers. It uses modular exponentiation and witnesses to determine if a number is composite or probably prime. With enough deterministic witnesses, it is provably correct for numbers up to certain bounds.
This tool uses JavaScript BigInt for all calculations, so there is no practical integer overflow limit. Numbers up to hundreds of digits can be tested. For very large numbers (15+ digits), the Miller-Rabin algorithm is used automatically for speed.
Integer factorization decomposes a composite number into a product of prime numbers. For example, 360 = 2³ × 3² × 5. This is the mathematical foundation of RSA encryption — factoring large numbers (hundreds of digits) is computationally infeasible with current algorithms.