Math BasicsMore About Numbers |
What is the Sieve of Eratosthenes? |
The smallest prime numbers—those less than 1 million—can be determined using something invented circa 240 B.C.E.: the Sieve of Eratosthenes (note: the largest primes are found using Lagrange’s Theorem from group theory studies). This method was named after astronomer and mathematician Eratosthenes of Cyrene (276-196 B.C.E.), who was actually more famous for calculating the circumference of the Earth than for his work with prime numbers.
To determine primes using this method, make a list of all the integers less than or equal to n (numbers greater than 1) and get rid of all the multiples of all primes less than or equal to the square root of n. The numbers that are left are all primes. For example, to determine primes less than 100, start with 2 as the first prime; then write all odd numbers from 3 to 100 (there is no need to write the even numbers). Take 3 as the first prime and cross out all its multiples in the numbers you listed. Take the next number, 5, and then 7, and cross out all their multiples. By the time you reach 11, many numbers will be eliminated and you will have reached a number greater than the square root of 100 (11 is greater than 10, the square root of 100). Thus, all the numbers you have left will be primes.