Understanding the results
The table below shows the three outputs for sample inputs.
| Input | Prime? | Factorization | Next prime |
|---|---|---|---|
| 97 | Yes | 97 | 101 |
| 84 | No | 2 x 2 x 3 x 7 | 89 |
| 100 | No | 2 x 2 x 5 x 5 | 101 |
| 2 | Yes (only even prime) | 2 | 3 |
| 1 | No (neither prime nor composite) | - | 2 |
- The number 1 is not prime: primes must have exactly two distinct divisors, and 1 has only one. Excluding 1 preserves the uniqueness of prime factorization.
- Trial division is exact but slows for very large inputs; this calculator accepts numbers up to 10^12, where the search tests divisors up to one million.
- The next-prime search is guaranteed to terminate quickly in this range: by Bertrand's postulate there is always a prime between n and 2n.
What is a prime number?
A prime number is a natural 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 and 29. The number 2 is the only even prime, since every other even number is divisible by 2. Numbers greater than 1 that are not prime are called composite; the number 1 is neither prime nor composite, by definition.
The fundamental theorem of arithmetic states that every integer greater than 1 can be written as a product of primes in exactly one way, apart from the order of the factors. This unique prime factorization is why primes are called the building blocks of the integers: 84 = 2^2 x 3 x 7, and no other combination of primes multiplies to 84.
Primes are infinite in number — a result proved by Euclid around 300 BC — and they become sparser as numbers grow, though without any simple pattern. Large primes underpin modern public-key cryptography (such as RSA), which relies on the practical difficulty of factoring the product of two very large primes.
How to use this prime number calculator
- Enter a whole number n of at least 1. Decimals are rounded down to the nearest whole number.
- Read the primality verdict: a check mark means the number is prime, a cross means it is composite (or 1, which is neither).
- Read the prime factorization — the unique product of primes equal to your number. For a prime input, the factorization is the number itself.
- Read the next prime, the smallest prime strictly greater than your number.
How primality is tested: trial division
A number n is composite if and only if it has a divisor greater than 1 and at most the square root of n. This is because divisors pair up: if n = a x b with a <= b, then a <= sqrt(n). Trial division therefore only needs to test candidate divisors up to sqrt(n) — after checking 2, only odd candidates are needed.
Worked example (prime): n = 97. The square root of 97 is about 9.85, so it suffices to test 2, 3, 5, 7 and 9. 97 is odd; 9 + 7 = 16 is not divisible by 3; it does not end in 0 or 5; 97 / 7 = 13.857...; and 97 / 9 is not whole. No divisor exists, so 97 is prime.
Worked example (factorization): n = 84. Divide out primes from smallest up: 84 / 2 = 42, 42 / 2 = 21, 21 / 3 = 7, and 7 is prime. So 84 = 2 x 2 x 3 x 7 = 2^2 x 3 x 7. The next prime after 84 is 89 (85 = 5 x 17, 86 = 2 x 43, 87 = 3 x 29, 88 = 2^3 x 11).
Common mistakes
- Counting 1 as a prime number — by definition a prime has exactly two distinct divisors, and 1 has only one.
- Assuming all primes are odd: 2 is prime, and it is the only even prime.
- Testing divisors all the way up to n instead of stopping at sqrt(n) — any composite number has a factor at or below its square root.
- Believing all odd numbers are prime: 9 = 3 x 3, 15 = 3 x 5 and 21 = 3 x 7 are odd composites.
- Confusing prime factorization with any factorization: 84 = 4 x 21 is a factorization, but the prime factorization is 2 x 2 x 3 x 7.
よくある質問
How do I check if a number is prime?
Test whether any integer from 2 up to the square root of the number divides it evenly. If none does, the number is prime. For 97, the square root is about 9.85, and none of 2, 3, 5, 7 or 9 divides 97, so 97 is prime. Divisor pairs guarantee that any composite number has a factor at or below its square root.
Why is 1 not a prime number?
A prime is defined as having exactly two distinct positive divisors, 1 and itself; the number 1 has only one divisor. The definition also protects the fundamental theorem of arithmetic: if 1 were prime, factorizations would no longer be unique (6 = 2 x 3 = 1 x 2 x 3 = 1 x 1 x 2 x 3, and so on).
What is a prime factorization?
It is the expression of a number as a product of prime numbers, which the fundamental theorem of arithmetic guarantees is unique apart from ordering. For example, 84 = 2 x 2 x 3 x 7. To find it, repeatedly divide out the smallest prime that goes in evenly until the remaining quotient is 1 or prime.
Is 2 a prime number?
Yes — 2 is prime because its only divisors are 1 and 2, and it is the only even prime. Every other even number is divisible by 2 and therefore composite. This is why primality tests handle 2 separately and then check only odd candidates.
How many prime numbers are there?
Infinitely many, as Euclid proved around 300 BC: given any finite list of primes, the number formed by multiplying them all and adding 1 is divisible by none of them, so some prime is missing from the list. Primes thin out as numbers grow — by the prime number theorem, the density of primes near n is roughly 1 / ln(n) — but they never stop.
Why do prime numbers matter in cryptography?
Public-key systems such as RSA rest on an asymmetry: multiplying two large primes is easy, but recovering the primes from their product is computationally hard at the sizes used in practice (hundreds of digits). Security keys are built from such products, so prime generation and primality testing are core cryptographic operations.
参考文献
- Weisstein, Eric W. "Prime Number" and "Fundamental Theorem of Arithmetic." MathWorld — A Wolfram Web Resource. mathworld.wolfram.com.
- Hardy GH, Wright EM. An Introduction to the Theory of Numbers. Oxford University Press (primes, unique factorization, Bertrand's postulate).
- Euclid. Elements, Book IX, Proposition 20 (infinitude of primes).