Click to show tips
Pick a scenario to see how the calculator works, then adjust the values
Factor 360, a highly composite number with many divisors.
Key values: 360 = 2^3 x 3^2 x 5 · 24 divisors · phi(360) = 96
Check if 7919 is prime (it is -- the 1000th prime number).
Key values: 7919 is prime · 2 divisors · phi(7919) = 7918
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
Enter an integer greater than 1 to see its prime factorization, factor tree, and divisors.
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.
The simplest primality test: check if any integer from 2 to divides :
Why only up to ? If and both and , then — a contradiction. So at least one factor must be ≤ .
| Number | Check up to | Divisors found? | Prime? |
|---|---|---|---|
| 97 | None (2,3,5,7) | Yes | |
| 91 | 7 × 13 | No | |
| 1,009 | None | Yes |
The Prime Number Theorem states that the number of primes up to is approximately:
| 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.
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).
Test whether any integer from 2 to divides evenly. If none do, the number is prime. You only need to check up to because if and both and exceed , then , which is a contradiction.
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.
There are infinitely many primes. Euclid proved this around 300 BCE. The Prime Number Theorem shows that the number of primes up to is approximately . For instance, about 5.1% of integers up to are prime.
The largest known primes are Mersenne primes of the form . As of 2024, the largest known prime is , which has over 41 million digits. Finding new record primes is an active area of computational mathematics.
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.