Prime Number Checker
Enter any whole number up to one trillion and instantly find out whether it is prime or composite. The calculator also shows the smallest prime factor and the complete prime factorization with an explanation.
Is This Number Prime?
Prime Number Checker Formula
Where:
- \(n\) — the whole number being tested
- \(d\) — a candidate divisor
- \(\sqrt{n}\) — the square root of \(n\), rounded down to the nearest integer
The formula expresses the trial division test: it is enough to search for divisors up to \(\sqrt{n}\), because if \(n = a \times b\) with both factors greater than 1, at least one of them cannot exceed \(\sqrt{n}\). This is why the calculator only tests candidates up to the square root, skipping multiples of 2 and 3 (it checks 2, 3, and then numbers of the form \(6k \pm 1\)).
Prime Number Checker – Calculation Example
Example: is 91 a prime number? We test candidate divisors up to \(\sqrt{91} \approx 9.54\), so only 2, 3, 5 and 7 need to be checked.
\[ 91 \div 2 = 45.5 \quad (\text{not a divisor}) \]
\[ 91 \div 3 = 30.\overline{3} \quad (\text{not a divisor}) \]
\[ 91 \div 5 = 18.2 \quad (\text{not a divisor}) \]
\[ 91 \div 7 = 13 \quad (\text{exact — 7 is a divisor!}) \]
Result: 91 is a composite number. Its smallest prime factor is 7, since \(91 = 7 \times 13\), and the full prime factorization is \(91 = 7 \times 13\).
How to Use the Prime Number Checker
- Enter the whole number you want to test in the Number to check (n) field. Any integer from 0 to 1,000,000,000,000 (1012) is accepted.
- Read the Result — prime or composite line for the verdict. Numbers below 2 are reported as neither prime nor composite.
- If the number is composite, check A prime factor (shown if composite) — this is the smallest prime that divides your number, together with its cofactor.
- Read the Full prime factorization and explanation section, which breaks the number into prime factors and explains how the answer was verified.
What Is a Prime Number?
A prime number is a whole number greater than 1 that has exactly two positive divisors: 1 and itself. The first primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Every other whole number greater than 1 is composite, meaning it can be written as a product of two smaller whole numbers, both greater than 1.
The number 2 deserves a special mention: it is the only even prime, since every other even number is divisible by 2. The numbers 0 and 1 are neither prime nor composite — 1 has only one divisor, and 0 is divisible by every positive integer, so neither fits the definition of "exactly two divisors."
Prime numbers are the building blocks of arithmetic. The fundamental theorem of arithmetic states that every whole number greater than 1 factors into primes in exactly one way (apart from the order of the factors). That is why the calculator shows the complete prime factorization whenever the number is composite: it tells you exactly which prime building blocks make up your number, and how many times each appears.
Interpreting the result is straightforward. If the verdict is prime, the number cannot be broken down further. If it is composite, the smallest prime factor shown is the easiest way to prove it — dividing your number by that factor yields a whole number, which immediately rules out primality.
Assumptions, Limitations and Tips
- Range: the calculator accepts integers from 0 to 1012. Larger numbers require more advanced methods.
- Method: it uses trial division with the \(6k \pm 1\) optimization, which is fast and gives a mathematically certain answer for numbers in the supported range. Probabilistic tests such as Fermat's Little Theorem are used instead for astronomically large numbers, because trial division becomes too slow even though it is exact.
- Decimals and negatives: primality is defined only for whole numbers greater than 1, so decimal entries, negative numbers, and 0 or 1 return an explanation rather than a verdict.
- Quick manual checks: before using the calculator, you can often rule out primality mentally — a number ending in 0, 2, 4, 5, 6 or 8 is divisible by 2 or 5, and a number whose digits sum to a multiple of 3 (as with 91, since 9 + 1 = 10... check: 10 is not divisible by 3, so that shortcut fails here) is divisible by 3. The digit-sum test relates to the digital root.
- Why factorization matters: prime factorizations are the foundation of many number-theory tools, from the multiplicative inverse modulo n used in cryptography to solving congruence systems with the Chinese Remainder Theorem.
Frequently Asked Questions
How can I check if a number is prime by hand?
Test whether any whole number from 2 up to \(\sqrt{n}\) divides your number evenly. If none does, the number is prime. For 137, \(\sqrt{137} \approx 11.7\), so you only check 2, 3, 5, 7 and 11 — none divides it, so 137 is prime. Skip even candidates after checking 2 to save time, and remember you never need to test beyond the square root.
Why is 1 not a prime number?
A prime must have exactly two positive divisors: 1 and itself. The number 1 has only one divisor, so it fails the definition. This convention also keeps the fundamental theorem of arithmetic true — every number greater than 1 would have infinitely many factorizations like \(6 = 2 \times 3 = 2 \times 3 \times 1\) if 1 counted as prime. So 1 is neither prime nor composite.
What are the quickest divisibility tricks before testing?
Check the last digit: numbers ending in 0, 2, 4, 5, 6 or 8 are divisible by 2 or 5. Add the digits — if the sum is divisible by 3, so is the number (for 87: \(8 + 7 = 15\), divisible by 3, so 87 is composite). For 11, alternately add and subtract the digits; a result divisible by 11 means the number is too. These rules instantly eliminate most composites.
What is the difference between prime and coprime numbers?
Primality is a property of a single number: it has exactly two divisors. Being coprime (relatively prime) is a property of a pair: two numbers are coprime when their greatest common divisor is 1. For example, 8 and 15 are both composite, yet they are coprime because \(\gcd(8, 15) = 1\). Note that 2 and 3 are coprime, but so are 4 and 9 — neither needs to be prime itself.
What are common numbers that look prime but are not?
Famous "pseudoprimes" include 91 (\(= 7 \times 13\)), 57 (\(= 3 \times 19\)), 51 (\(= 3 \times 17\)), 87 (\(= 3 \times 29\)) and 119 (\(= 7 \times 17\)). People miss them because they are not divisible by 2, 5, or an obvious square. When checking by hand, always test 3 (digit sum), 7 and 11 carefully — these catch most of the tricky cases under 150.
How do I find the prime factorization of a number step by step?
Repeatedly divide by the smallest prime that fits. For 360: divide by 2 to get 180, by 2 to get 90, by 2 to get 45; 45 is not even, so divide by 3 to get 15, and by 3 to get 5. This gives \(360 = 2^3 \times 3^2 \times 5\). Continue until the remainder is itself prime. Each division step is guaranteed to work on some prime because of the fundamental theorem of arithmetic.
Are there infinitely many prime numbers?
Yes — Euclid proved this around 300 BC. Suppose there were a largest prime, multiply all known primes together and add 1; the result is not divisible by any of them, so it must have a new prime factor. There are 78,498 primes below one million and about \(\pi(10^{12}) \approx 37.6\) billion below one trillion. Prime gaps grow on average, but new record primes keep being discovered — over 24 million digits long as of recent finds.