Prime numbers

Definition, the sieve of Eratosthenes, trial division up to the square root, prime factorisation, number of divisors and the infinitude of primes.

The outline, topic by topic

Each topic is weighted the way the exam weighs it.

Prime number: what is it?
Show the answer
An integer greater than or equal to 2 that has exactly two positive divisors: 1 and itself.
2 is the only even prime. An integer greater than 1 that is not prime is called composite: 91 = 7 × 13 is one, although it is divisible by neither 2, 3 nor 5.
Is 221 a prime number?
- No: 221 = 13 × 17
- Yes: none of 2, 3, 5, 7 or 11 divides it
- No: 221 is divisible by 3
- Yes: it is odd and ends in 1
Show the answer
No: 221 = 13 × 17
You must try the primes up to √221 ≈ 14.9, so up to 13 inclusive: stopping at 11 leads to an error. 13 × 17 = 221.
An integer n greater than 1 that is divisible by no integer from 2 to … is prime.
Show the answer
An integer n greater than 1 that is divisible by no integer from 2 to √n is prime.
For 221, √221 ≈ 14.9: trying up to 13 is enough, and 13 divides 221 (221 = 13 × 17).
Fundamental theorem of arithmetic: what is it?
Show the answer
Every integer greater than or equal to 2 is a product of primes, and this product is unique up to the order of the factors.
360 = 2³ × 3² × 5 is the only factorisation of 360. Uniqueness is what lets us read GCD, LCM and the number of divisors from the exponents.