Prime Numbers: Euclid and Eratosthenes

After Euclid’s theorem on the infinitude of primes, the sieve of Eratosthenes is explained, and backed up with concrete results from a Pythod program. There is also a detailed description of the Meissel–Lehmer partial sieving method for the counting of primes, and the factorisation methods of Fermat and Pollard. Probabilistic primality tests, including the AKS test, one-way function and RSA public-key encryption are also covered.