Quickly recall that a prime number is a number larger than 1 that is divisible only by itself and 1 (e.g. 2, 5, 7, 11...). Euclid showed that there are an infinite number of primes. However, it wasn't until around 240 B.C. that Eratosthenes developed the first known method for finding primes, a method known today as the Sieve of Eratosthenes.
The Sieve can be used to find all prime numbers up to a given integer, n.
The method is straightforward: make a a list of all the integers less than or equal to n, cross out the multiples of all primes that are less than or equal to the square root of n, the numbers that remain are the primes. Typically it is easiest to start with 2, cross out all multiples of 2. Then 3, cross out all its multiples etc.
An example with n = 120 is demonstrated the video below. The video crosses out the multiples of 2, then of 3, then of 5 and lastly the multiples of 7 (since 7 is the largest prime that is less than the square root of 120). After 7, the video highlights the remaining primes in pink.
 |
| By Ricordisamoa (Own work) [CC-BY-SA-3.0 (http://creativecommons.org/licenses/by-sa/3.0)], via Wikimedia Commons |
Prime numbers continue to fascinate mathematicians today. Some of the most famous unsolved problems in mathematics center around prime numbers, including the Goldbach Conjecture and the Riemann Hypothesis.
No comments:
Post a Comment