Prime numbers explained: how to test, list and use them

A prime number is a whole number greater than 1 whose only divisors are 1 and itself. The first few are 2, 3, 5, 7, 11 and 13. Every other whole number above 1 is composite: it can be broken into smaller factors, and ultimately into primes. The prime number checker tests and factorises numbers and lists primes, and this guide explains the ideas it uses.

What a prime number is

Seven is prime because nothing divides it evenly except 1 and 7. Nine is not, because 9 = 3 × 3. Two facts surprise people:

• 1 is not prime. It has only one divisor, and if it counted as prime, factorisations would stop being unique: 6 could be 2 × 3, or 1 × 2 × 3, or 1 × 1 × 2 × 3.
• 2 is the only even prime. Every other even number is divisible by 2.

There are 25 primes below 100: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 and 97.

Testing a number

The direct test is trial division: try dividing by each prime in turn. You only need to go up to the square root of the number, because if n = a × b, one of a and b must be no bigger than √n. To test 97, √97 ≈ 9.85, so you only try 2, 3, 5 and 7. None divides it, so 97 is prime. To test 91, you find 91 = 7 × 13, a number that looks prime but is not.

Quick checks rule out most numbers instantly: an even last digit means divisible by 2, a last digit of 0 or 5 means divisible by 5, and a digit sum divisible by 3 means the number is too. The checker uses trial division, which is instant for anything up to a trillion, the limit it accepts, and it also shows the nearest primes above and below.

The sieve of Eratosthenes

To list every prime up to a limit, there is a faster method from ancient Greece. Write out the numbers from 2 upwards. Circle 2, then cross out every multiple of 2. The next number not crossed out, 3, is prime, so circle it and cross out its multiples. Continue with 5, then 7. Two shortcuts make it efficient:

• for each prime p you can start crossing out at p², because smaller multiples were already crossed out by smaller primes;
• you can stop once p² passes the limit; every number still standing is prime.

For 100, that means sieving with just 2, 3, 5 and 7. The tool's list uses exactly this sieve, up to 100,000, where there are 9,592 primes.

Prime factorisation

The fundamental theorem of arithmetic says every whole number above 1 can be written as a product of primes in exactly one way, apart from order. 360 = 2³ × 3² × 5, and 1001 = 7 × 11 × 13. That is why primes are often called the building blocks of numbers. Factorisations make other jobs easy: the GCD and LCM calculator finds common factors and multiples, and the divisors calculator lists every divisor and counts them from the factorisation.

How many primes there are

There are infinitely many primes, and the proof is over 2,000 years old. Euclid's argument: multiply any finite list of primes together and add 1. The result leaves remainder 1 when divided by each prime on the list, so its prime factors must be new. No list can ever be complete.

Primes thin out as numbers grow. There are 25 below 100, 168 below 1,000 and 78,498 below a million. The prime number theorem says that near a large number n, roughly one number in every ln n is prime, where ln is the natural logarithm. The largest known primes are Mersenne primes of the form 2ᵖ − 1, with tens of millions of digits, found by volunteer computing projects.

Where primes are used

The most important use is cryptography. Multiplying two large primes is easy, but recovering them from the product is extremely hard when the primes are hundreds of digits long. RSA encryption relies on that gap, together with arithmetic on remainders explained in Modulo explained: remainders, clocks and negative numbers and handled exactly by the modulo calculator. Primes also appear in hash table sizes, random number generators and check-digit schemes, all places where avoiding shared factors keeps patterns from repeating.