Eratosthenes of Cyrene
Eratosthenes of Cyrene lived from 276 BC to 194 BC.
He was born in Cyrene, North Africa which is now part of Libya. He studied in
Cyrene, later in Greece, and was eventually appointed the third librarian of the
prestigious Library of Alexandria. Eratosthenes was a general mathematician who
did well in many fields, but was never the highest expert in a field. He got
the nickname Beta[1] which commented on him always coming in second and not
first. He is most remembered for the Sieve of Eratosthenes; however, he had
several other accomplishments. He was the first person to reasonably
approximate the circumference of the Earth, and he also provided a mechanism
for solving the “duplicating the cube” problem, which was a famous problem of
the time. Much of his work, however, has been lost, and information about him
is instead derived from other sources.
The Sieve of Eratosthenes is the first known algorithm for
generating prime numbers. It can be used to test if a number is prime, or to
find all the prime numbers less than or equal to a number. It works by
eliminating all the composite numbers less than or equal to the number. The first
step in the algorithm is to list all the natural numbers from two up to and including
the number being tested (n). Next, starting at the beginning of the list, find
the first number that is not crossed out, and cross out all of its multiples.
After this, proceed to the next number that is not crossed out and cross out
its multiples. Repeat this process until you reach the square root of the
number you are examining. Any number that is not crossed out at the end is
prime. The algorithm is best explained with an example:
Take n = 29
1) List the numbers from 2 to n
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29
2) Start at the beginning of the list and find the first number not crossed out, then cross out its multiples.
2,
3, 4, 5, 6, 7, 8,
9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
21, 22, 23, 24, 25, 26, 27, 28, 29
3) Repeat this process up to the square root of n
2, 3,
x, 5, x, 7, x, 9, x, 11, x, 13, x, 15, x, 17, x, 19, x, 21,
x, 23, x, 25, x, 27, x, 29
2, 3, x, 5,
x, 7, x, x, x, 11, x, 13, x, x, x, 17, x, 19, x, x, x, 23, x, 25, x, x,
x, 29
4) The numbers that are left are
prime: 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29
The Sieve of Eratosthenes is not the most efficient algorithm for finding primes, however, it is still one of the most efficient algorithms for generating all the prime numbers less than a relatively small number (less than a billion)[2]. According to Pritchard[2] it is often faster for a computer to generate a list of these prime numbers than to read them from a disk.
The stopping condition of the square root of n may
not have been proposed by Eratosthenes himself, but rather added later. Another
number theory property that can be used to increase the performance of the
algorithm is that when checking the multiples of a number (i), the first
multiple that needs checked is i2 because any smaller
multiples would have been crossed out already because of their smaller divisor.
The limitation of the algorithm is not in computational complexity, however,
but rather in memory space. The algorithm has a complexity of O( (n log n)(log
log n) ) bit operations, and has an O(n) memory requirement[2]. With current
computers, the memory is limiting factor.
Several modifications have been made to the Sieve of
Eratosthenes to make algorithms that are more computational and memory
efficient. The Sieve of Atkins and the Linear Segmented Wheel Sieve[2] are two of
these improved algorithms. An implementation of the Sieve of Atkins can find
all the primes less than a billion in 8 seconds with a 350Mhz computer[2]. Interestingly,
it then takes 35 seconds to convert all these primes into decimal and display
them on the screen.
Prime numbers are an important tool in modern cryptography. The Sieve of Eratosthenes and its variations are not efficient enough to deal with very large prime numbers; however, they are still used in checking if a number is prime. Using the trial division method of test if a number is prime requires a list of prime numbers less than the square root of the number being check. A sieve algorithm is often used to generate this list. Trial division itself is no longer directly used to check if a number is prime, but rather is used to prescreen large numbers before other tests are applied.
*For
a good site on testing if a number is prime, check out reference [2].
1) O’Connor, J. J. and Robertson, E. F. “Eratosthenes of Cyrene.” January, 1999. Retrieved Sept, 2004 from http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Eratosthenes.html
2) P. Pritchard, "Linear prime-number sieves: a family tree," Sci. Comput. Programming, 9:1 (1987) 17--35. MR 88j:11087 [A comparison of recent sieves such as the sieve of Eratosthenes.]
http://www.utm.edu/research/primes/references/refs.cgi/Pritchard87
http://primes.utm.edu/glossary/page.php?sort=SieveOfEratosthenes