Prime Number Checker

Last updated: 2026-05-18

Prime numbers

A prime number is a natural number greater than 1 whose only positive divisors are 1 and itself. That means no other integer divides it evenly.

• 2 is prime: divisible only by 1 and 2.
• 7 is prime: divisible only by 1 and 7.
• 12 is not prime (composite): divisible by 1, 2, 3, 4, 6, and 12.

The first twenty primes are:

$2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29,\ 31,\ 37,\ 41,\ 43,\ 47,\ 53,\ 59,\ 61,\ 67,\ 71$

Primes become less frequent as numbers get larger — there are 25 primes below 100, 168 below 1000, and 78,498 below one million — yet they never stop. Euclid proved around 300 BCE that the list of primes is infinite.

Why 1 is not prime

The number 1 is sometimes thought to be prime because its only divisors are 1 and itself. The modern definition, however, requires exactly two distinct positive divisors, and 1 has only one (itself).

The deeper reason is mathematical consistency: excluding 1 preserves the Fundamental Theorem of Arithmetic, which states that every integer greater than 1 has a unique prime factorization. If 1 were prime, then:

$12 = 2^2 \times 3 = 1 \times 2^2 \times 3 = 1^2 \times 2^2 \times 3 = \ldots$

There would be infinitely many factorizations for the same number, destroying uniqueness. By convention, 1 is called a unit — neither prime nor composite.

Trial division

For numbers in the range 1–1000, this calculator uses trial division — checking divisibility by each prime up to $\sqrt{1000} \approx 31.6$. If a number $n$ has no prime factor at or below its square root, then $n$ itself is prime.

The primes up to 31 are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31. Checking divisibility by all eleven of these is sufficient to determine primality for any integer up to $31^2 = 961$ and, combined with a direct check for those primes themselves, covers the full 1–1000 range.

Example — is 97 prime?

Divisor	$97 \div d$	Remainder
2	48.5	1
3	32.3…	1
5	19.4	2
7	13.857…	6

None of the primes up to $\sqrt{97} \approx 9.8$ divide 97 evenly, so 97 is prime.

Example — is 91 prime?

$91 \div 7 = 13$ with remainder 0. Because 7 divides 91, the number is composite — specifically $91 = 7 \times 13$. The smallest prime factor shown is 7.

The Sieve of Eratosthenes

For finding all primes up to a limit, trial division applied one number at a time is less efficient than the Sieve of Eratosthenes, devised in ancient Greece. The procedure:

1. List every integer from 2 to $N$.
2. Starting at 2, cross out all multiples of 2 (4, 6, 8, …).
3. Advance to the next uncrossed number (3) and cross out its multiples (6, 9, 12, …).
4. Continue until the next uncrossed number exceeds $\sqrt{N}$. All remaining uncrossed numbers are prime.

The sieve runs in $O(N \log \log N)$ time — dramatically faster than checking each number individually when building a large table of primes.

Primes in cryptography

Nearly all public-key cryptography depends on a striking asymmetry: multiplying two large primes is computationally fast, but factoring their product back into the original primes is computationally hard — practically infeasible for primes with hundreds of digits.

RSA encryption, used in HTTPS, SSH, and digital signatures, exploits this gap:

1. Choose two large primes $p$ and $q$ (each typically 1024–4096 bits).
2. Compute $n = p \times q$. Publish $n$ as part of the public key.
3. An attacker who wishes to break the key must factor $n$ — finding $p$ and $q$ given only $n$. With current algorithms, this would take longer than the age of the universe for sufficiently large primes.

Primes also appear in Diffie–Hellman key exchange, elliptic-curve cryptography, and hash functions. The security of the modern internet rests, in part, on the difficulty of prime factorization.

Quick reference

Number	Prime?	Smallest factor
1	No (unit)	—
2	Yes	2 (itself)
4	No	2
17	Yes	17 (itself)
49	No	7
97	Yes	97 (itself)
100	No	2
997	Yes	997 (itself)

Frequently Asked Questions (FAQ)

What is a prime number?

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. For example, 2, 3, 5, 7, 11, and 13 are all prime. The number 12 is not prime because it is divisible by 2, 3, 4, and 6. Every integer greater than 1 is either prime or can be expressed uniquely as a product of primes — a result known as the Fundamental Theorem of Arithmetic.

Why is 1 not a prime number?

The modern definition of a prime requires exactly two distinct positive divisors: 1 and itself. The number 1 has only one positive divisor (itself), so it falls short.

Excluding 1 also preserves the uniqueness of prime factorization. If 1 were prime, the same number would have infinitely many factorizations: 12 = 2 × 2 × 3 = 1 × 2 × 2 × 3 = 1 × 1 × 2 × 2 × 3 …

What are the first ten prime numbers?

The first ten primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29. The number 2 is the only even prime; every other even number is divisible by 2 and therefore composite. Primes become progressively rarer as numbers grow larger, though they never stop — Euclid proved around 300 BCE that there are infinitely many primes.

Why do primes matter in cryptography?

Most public-key cryptography — including RSA, the protocol behind HTTPS and digital signatures — relies on the fact that multiplying two large primes together is fast, but factoring the result back into those two primes is computationally infeasible. A typical RSA key uses primes with hundreds of digits. The asymmetry between multiplication (easy) and factoring (hard) is what makes encrypted communication secure.