Every whole number greater than 1 is either prime, or can be written as a product of primes in exactly one way. That uniqueness is the fundamental theorem of arithmetic, and it is why primes are called the building blocks of the integers.
Trial division
Divide by 2 as often as it goes, then 3, then 5, and so on upward. You only ever need to test up to the square root of what remains: if a number has a factor larger than its square root, the matching cofactor is smaller than the square root and you would have found it already.
Counting divisors without listing them
Once you have the factorisation, the number of divisors follows immediately. If n = p₁^a × p₂^b × …, then each divisor picks an exponent from 0 to a for the first prime, 0 to b for the second, and so on:
For 5040 = 2⁴ × 3² × 5 × 7 that gives 5 × 3 × 2 × 2 = 60 divisors. Listing them by hand would take a while; the factorisation gives it in one line.
Why this is computationally hard
Checking whether a number is prime is fast. Actually factorising a large one is not, and no efficient general algorithm is known. Trial division on a 600-digit number would outlast the universe.
RSA encryption rests entirely on this asymmetry. Multiplying two large primes is instant; recovering them from the product is infeasible. The public key is the product, and the private key is the pair of factors. If someone found a fast factorisation algorithm, most of the internet’s encryption would fall over — which is also why quantum computing attracts so much attention, since Shor’s algorithm factors efficiently on hardware that does not yet exist at the necessary scale.
Useful facts about primes
- 2 is the only even prime. Every other even number has 2 as a factor.
- 1 is not prime, by definition — including it would break the uniqueness of factorisation.
- There are infinitely many primes, proved by Euclid around 300 BC.
- Primes thin out but never stop; near a large number n, roughly 1 in ln(n) integers is prime.