What makes a number prime
A prime number is a positive integer greater than one with exactly two positive divisors: 1 and the number itself. Two, three, five, seven, and eleven are the first primes. A composite number is greater than one and has at least one additional divisor.
The number 1 is neither prime nor composite. It has only one positive divisor rather than two. Zero is also neither, and negative integers are outside the usual elementary definition of primes.
Prime numbers are the multiplicative building blocks of the positive integers. Every integer greater than one can be written as a product of primes, and that factorization is unique apart from the order of the factors.
Quick divisibility checks
Small rules can identify many composite numbers immediately. Every even number above two is composite. A number whose decimal digits sum to a multiple of three is divisible by three. A number ending in zero or five is divisible by five unless it is five itself.
For example, 12,345 has digit sum 1 + 2 + 3 + 4 + 5 = 15, so it is divisible by three. It also ends in five, so it is divisible by five. No advanced test is required.
These shortcuts prove compositeness when they find a divisor, but failing a shortcut does not prove primality. A number can avoid divisibility by 2, 3, and 5 while still being a product such as 7 × 11 = 77.
Trial division
The direct way to test n is to try dividing it by possible factors. It is enough to test through the square root of n. If n = a × b and both a and b were greater than the square root, their product would exceed n. Therefore every composite number has at least one factor no larger than its square root.
After checking 2, only odd candidates need testing. Better implementations test known primes rather than every odd number. Trial division is simple and produces an actual factor, which makes it excellent for small inputs.
Its weakness is scale. The square root of a 64-bit number can be several billion. Trying billions of divisors in a browser would be unnecessarily slow, so this calculator uses a faster primality test and searches only a small range when offering a sample factor.
Miller–Rabin testing
Miller–Rabin uses modular arithmetic to find evidence that a number is composite. For an odd candidate n, write n − 1 as d multiplied by a power of two, with d odd. A chosen base is raised to d modulo n, then repeatedly squared.
Prime numbers must follow a particular pattern under this calculation. A base that violates the pattern is a witness proving that n is composite. Passing one base usually means “probably prime,” because some composites can fool a particular base.
For bounded integers, however, researchers have identified witness sets sufficient to catch every composite in the range. This tool uses the bases 2, 325, 9,375, 28,178, 450,775, 9,780,504, and 1,795,265,022. Within the unsigned 64-bit range, passing all of them gives a deterministic result.
Why exact integer arithmetic matters
JavaScript’s ordinary number type is a binary floating-point value. It represents integers exactly only through 9,007,199,254,740,991. Above that safe-integer boundary, distinct integers can round to the same stored value.
A primality test cannot tolerate that rounding. One changed unit can turn a prime into a composite or the reverse. The checker therefore parses input as BigInt and performs multiplication, remainder, and exponentiation with exact integers.
The accepted maximum is 18,446,744,073,709,551,615, which is 2 to the 64th power minus one. The limit matches the deterministic guarantee of the selected witnesses, not the storage ability of BigInt.
Modular exponentiation
Miller–Rabin needs large powers modulo n. Calculating the full power first would create an enormous intermediate value. Repeated squaring keeps every step reduced modulo n.
If an exponent is written in binary, square the base for each bit and multiply it into the result only when that bit is one. The number of steps grows with the logarithm of the exponent rather than with the exponent itself.
This method is called binary exponentiation or exponentiation by squaring. It makes tests on 64-bit values quick enough to update interactively in the browser.
Worked examples
The number 97 is prime. Trial division only needs to consider primes through the square root of 97, which is less than ten: 2, 3, 5, and 7. None divides 97, so no factor pair exists.
The number 221 is composite. It is not even, its digits do not sum to a multiple of three, and it does not end in five. Trial division finds 13, and 221 ÷ 13 = 17.
The number 104,729 is the 10,000th prime. A deterministic primality test confirms it without relying on its position in a stored table.
The maximum unsigned 64-bit integer, 18,446,744,073,709,551,615, is composite. Its decimal form ends in 615 and is divisible by 5. In fact it has many factors because it equals 2 to the 64th power minus one.
Prime factorization is a different task
Primality testing asks for a yes-or-no classification. Factorization asks for all prime factors and their exponents. Proving that a number is composite can be much easier than fully factoring it.
Miller–Rabin can show that a large value is composite without returning a factor. This tool looks for a divisor up to 10,000 to make simple results more informative, but it does not promise a complete factorization.
Advanced factorization methods include Pollard’s rho algorithm, the quadratic sieve, and the general number field sieve. Their performance depends strongly on the number’s size and structure.
Primes and cryptography
Large primes are used in several public-key systems and cryptographic protocols. The mathematics is real, but a general-purpose browser checker should not be used to generate production cryptographic keys.
Secure key generation requires a cryptographically secure random source, appropriate prime constraints, sufficient bit length, protection of intermediate values, and a reviewed implementation. Modern libraries and platform APIs handle those requirements.
A 64-bit prime is also far too small for common public-key security. This checker is educational and useful for ordinary integer work, not a key-generation service.
Prime gaps and density
There are infinitely many primes, but they become less frequent among larger integers. The prime number theorem says that numbers near n have a prime density of approximately one divided by the natural logarithm of n.
That is an average description, not a regular spacing rule. Consecutive primes can be close together, including twin primes differing by two, or separated by larger gaps. There is no simple repeating decimal pattern that marks every prime.
Randomly searching odd numbers and testing each candidate is nevertheless practical at many sizes because primes are sparse but not vanishingly rare.
Common misconceptions
All primes above three have the form 6k − 1 or 6k + 1, but not every number of those forms is prime. Twenty-five equals 6 × 4 + 1 and is composite. The form only removes obvious multiples of two and three.
A number not divisible by small primes is not automatically prime. The product of two large primes can evade a long list of small divisors.
Decimal appearance has little significance beyond divisibility shortcuts tied to base ten. A number ending in an unusual digit is not more likely to be prime after the necessary exclusions are considered.
Limits of the checker
The calculator accepts non-negative integers through the unsigned 64-bit maximum and gives a deterministic prime or composite result in that range. It does not accept decimals, scientific notation, negative signs, or integers beyond the stated bound.
When a composite has a factor at or below 10,000, that factor is shown. Absence of a displayed factor does not mean the number is prime; the separate Miller–Rabin result determines that. It only means the optional small-factor search did not find one.
For mathematical publication or cryptographic work, use proof-producing specialist software and retain the certificate or method details. For learning, programming checks, and everyday integer questions, the deterministic 64-bit result is a fast and exact answer.