| Math Logic |
|
|
| Question : |
|
How would you describe the Sieve of Eratosthenes ? |
Answer : |
|
The most effective known method of locating primes, this procedure separates the primes out of the set of all
whole numbers. |
|
It was created by Eratosthenes, an ancient Greek Mathematician. |
| Algorithm
: |
|
1. Write a list of numbers from 2 to the largest number you want to test for primality. Call this List A. |
|
|
2. Write the number 2, the first prime number, in another list for primes found. Call this List B. |
|
|
3. Strike off 2 and all multiples of 2 from List A. |
|
|
4. The first remaining number in the list is a prime number. Write this number into List B. |
|
|
5. Strike off this number and all multiples of this number from List A.
The crossing-off of multiples can be started at the square of the number, as lower multiples have already been crossed out in previous steps.
|
|
|
6. Repeat steps 4 and 5 until no more numbers are left in List A. Note that,
once you reach a number greater than the square root of the highest number in List A,
all the numbers remaining in List A are prime. |
