A prime number is a natural number greater than one whose only divisors are one and the number itself.
Prime numbers play a very important role in the fundamental theorem of arithmetic: every natural number greater than one is either a prime or a product of primes. Nowadays, number-theoretic algorithms are widely used, mainly due to cryptographic schemes based on large prime numbers. Most of those cryptographic schemes are based on the fact that we can efficiently find large primes, but we cannot factor the product of those large primes efficiently. As seen before, prime numbers play an important role in the implementation of hash tables.
The sieve of Eratosthenes is a simple and ancient algorithm to find all prime numbers up to a given limit. If we want to find all prime numbers up to N, we start by creating a list of consecutive integers from 2 to N (2, 3, 4, 5… N), initially unmarked. Let's use p to denote the smallest unmarked number. Then...