purpose

Primality Tester

Instantly check if any integer is prime or composite and see its full factorization.

Back to Prime Factorization Calculator

Prime Factorization Tips

Click to show tips

Try an Example

Pick a scenario to see how the calculator works, then adjust the values

Highly Composite Number

Factor 360, a highly composite number with many divisors.

Key values: 360 = 2^3 x 3^2 x 5 · 24 divisors · phi(360) = 96

Large Prime

Check if 7919 is prime (it is -- the 1000th prime number).

Key values: 7919 is prime · 2 divisors · phi(7919) = 7918

GCD and LCM

Compute the GCD and LCM of 84 and 120.

Key values: 84 = 2^2 x 3 x 7 · 120 = 2^3 x 3 x 5 · GCD = 12, LCM = 840

Documentation

What Is a Prime Number?

A prime number is a positive integer greater than 1 that has no positive divisors other than 1 and itself. The first primes are:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, …

Note: 1 is not prime (by convention, to preserve the uniqueness of prime factorization). 2 is the only even prime.

Trial Division

The simplest primality test: check if any integer from 2 to $\sqrt{n}$ divides $n$ :

\text{Check divisors: } 2, 3, 5, 7, 11, \ldots \leq \lfloor\sqrt{n}\rfloor

Why only up to $\sqrt{n}$ ? If $n = a \times b$ and both $a > \sqrt{n}$ and $b > \sqrt{n}$ , then $ab > n$ — a contradiction. So at least one factor must be ≤ $\sqrt{n}$ .

Number	Check up to	Divisors found?	Prime?
97	$\lfloor\sqrt{97}\rfloor = 9$	None (2,3,5,7)	Yes
91	$\lfloor\sqrt{91}\rfloor = 9$	7 × 13	No
1,009	$\lfloor\sqrt{1009}\rfloor = 31$	None	Yes

Distribution of Primes

The Prime Number Theorem states that the number of primes up to $n$ is approximately:

\pi(n) \approx \frac{n}{\ln n}

n	Primes up to n	n/ln(n)	% prime
100	25	22	25%
1,000	168	145	17%
1,000,000	78,498	72,382	7.8%
10⁹	50,847,534	48,254,942	5.1%

Primes become sparser as numbers grow, but they never run out — Euclid proved there are infinitely many.

Testing Large Numbers

Trial division becomes impractical for large numbers. Probabilistic tests like the Miller-Rabin test check primality in milliseconds for numbers with hundreds of digits. RSA encryption relies on the difficulty of factoring products of two large primes (2048+ bits).

Frequently Asked Questions

How do you check if a number is prime?

Test whether any integer from 2 to $\sqrt{n}$ divides $n$ evenly. If none do, the number is prime. You only need to check up to $\sqrt{n}$ because if $n = a \times b$ and both $a$ and $b$ exceed $\sqrt{n}$ , then $ab > n$ , which is a contradiction.

Is 1 a prime number?

No. By convention, 1 is excluded from the primes to preserve the uniqueness of prime factorization guaranteed by the Fundamental Theorem of Arithmetic. The smallest prime is 2, which is also the only even prime.

How many prime numbers are there?

There are infinitely many primes. Euclid proved this around 300 BCE. The Prime Number Theorem shows that the number of primes up to $n$ is approximately $n / \ln(n)$ . For instance, about 5.1% of integers up to $10^9$ are prime.

What is the largest known prime number?

The largest known primes are Mersenne primes of the form $2^p - 1$ . As of 2024, the largest known prime is $2^{136{,}279{,}841} - 1$ , which has over 41 million digits. Finding new record primes is an active area of computational mathematics.

Why are prime numbers important in cryptography?

RSA encryption relies on the fact that multiplying two large primes is fast, but factoring their product back into primes is computationally infeasible. A 2048-bit RSA key uses primes with roughly 300 digits each.

Related purpose Variants

Explore more purpose options

divisor-calculator

Divisor Calculator | Count and List All Divisors

Use this calculator

euler-totient

Euler\u2019s Totient Calculator | \u03C6(n) Function