In mathematics, the '''Sieve of Eratosthenes''' (Greek: κόσκινον Ἐρατοσθένους) is one of the most important number of prime number sieves. It is a simple test for finding all the prime numbers up to any given number.
+
In mathematics, the '''Sieve of Eratosthenes''' (Greek: κόσκινον Ἐρατοσθένους) is one of the most important number of prime number sieves. It is a simple test for finding all the prime numbers up to any given number.
The way it works is to repeatedly cross out the composite numbers, which are the multiples of each prime. Starting from the multiples of 2, to the square root of that given number. Afterwards, the numbers left that are not crossed off are prime numbers.
The way it works is to repeatedly cross out the composite numbers, which are the multiples of each prime. Starting from the multiples of 2, to the square root of that given number. Afterwards, the numbers left that are not crossed off are prime numbers.
−
With this method, the sieve of Eratosthenes can effectively find all of the smaller primes (below 10 million or so). The algorithm is named after Eratosthenes of Cyrene, a Greek mathematician.
+
With this method, the sieve of Eratosthenes can effectively find all of the smaller primes (below 10 million or so). The algorithm is named after Eratosthenes of Cyrene, a Greek mathematician.
−
[[File:Prime Numbers - The Sieve of Eratosthenes|thumb|right|335 px]]]
==Example of how to do the sieve==
==Example of how to do the sieve==
−
#List all the numbers from 1-100.
+
#[[File:Prime Numbers - The Sieve of Eratosthenes|thumb|right|335 px]]List all the numbers from 1-100.
#Cross out 1. It is a special number.
#Cross out 1. It is a special number.
#Encircle 2. Cross out all multiples of 2.
#Encircle 2. Cross out all multiples of 2.
Revision as of 11:56, 28 December 2013
In mathematics, the Sieve of Eratosthenes (Greek: κόσκινον Ἐρατοσθένους) is one of the most important number of prime number sieves. It is a simple test for finding all the prime numbers up to any given number.
The way it works is to repeatedly cross out the composite numbers, which are the multiples of each prime. Starting from the multiples of 2, to the square root of that given number. Afterwards, the numbers left that are not crossed off are prime numbers.
With this method, the sieve of Eratosthenes can effectively find all of the smaller primes (below 10 million or so). The algorithm is named after Eratosthenes of Cyrene, a Greek mathematician.
Example of how to do the sieve
Prime Numbers - The Sieve of Eratosthenes
List all the numbers from 1-100.
Cross out 1. It is a special number.
Encircle 2. Cross out all multiples of 2.
Encircle 3. Cross out all multiples of 3. Tip: Just add 6 to the first number, because all even numbers are crossed out.
Encircle 5. Cross out all multiples of 5.
Encircle 7. Cross out all multiples of 7.
Encircle all the rest of the numbers. They're prime.
