Difference between revisions of "Sieve of Eratosthenes"

(added a picture)
(thumb)
 
(3 intermediate revisions by 2 users not shown)
Line 1: Line 1:
===Description of the algorithm===
+
[[Image:Sieve.PNG|thumb|right|Sieve example for numbers up to 20]]
 +
The '''Sieve of Eratosthenes''' is a simple method to quickly uncover a short list of [[prime number]]s.
  
The Sieve of Eratosthenes is a simple method to quickly uncover a short list of primes. Begin by writing positive numbers starting with <math>2</math> up to the  maximal number you are interested in. Now, during each step, take the first number that is neither crossed, nor circled, circle it, and cross all larger numbers divisible by it.  Keep doing this until all numbers are either circled or crossed.  The circled numbers are the primes!
+
==Description of the algorithm==
 +
Begin by writing the [[positive integer]]s starting with <math>2</math> up to the  maximal number you are interested in. Now, during each step, take the first number that is neither crossed out nor circled, circle it, and cross all larger numbers [[divisibility | divisible]] by it.  Keep doing this until all numbers are either circled or crossed.  The circled numbers are the primes!
  
  
 
Below is an example of how to use this sieve to find the primes up to
 
Below is an example of how to use this sieve to find the primes up to
<math>20</math>. Note that after just two steps, no new crossouts appear. In general, one can forget about crossouts and start just circling all remaining numbers once a number exceeding the square root
+
<math>20</math>. Note that after just two steps, no new crossouts appear. In general, one can forget about crossouts and start just circling all remaining numbers once a number exceeding the [[square root]] of the maximal number we are interested in is circled (in our example it is <math>5>\sqrt{20}</math>). The reason is that if a number <math>n</math> is [[composite number | composite]], then it has a prime [[divisor]] not exceeding  <math>\sqrt n</math>.   
of the maximal number we are interested in is circled (in our example it is <math>5>\sqrt{20}</math>). The reason is that if a number <math>n</math> is composite, then it has a prime divisor not exceeding  <math>\sqrt n</math>.   
 
  
[[Image:Sieve.PNG|Sieve example for numbers up to 20]]
 
  
===Related Links===
+
==Related Links==
  
 
* [http://www.math.utah.edu/~pa/Eratosthenes.html Website with good visual example]
 
* [http://www.math.utah.edu/~pa/Eratosthenes.html Website with good visual example]
  
===See also===
+
==See also==
  
 
* [[Number theory]]
 
* [[Number theory]]
 
* [[Prime]]s
 
* [[Prime]]s
 +
 +
[[Category:Algorithms]]

Latest revision as of 20:16, 7 December 2007

Sieve example for numbers up to 20

The Sieve of Eratosthenes is a simple method to quickly uncover a short list of prime numbers.

Description of the algorithm

Begin by writing the positive integers starting with $2$ up to the maximal number you are interested in. Now, during each step, take the first number that is neither crossed out nor circled, circle it, and cross all larger numbers divisible by it. Keep doing this until all numbers are either circled or crossed. The circled numbers are the primes!


Below is an example of how to use this sieve to find the primes up to $20$. Note that after just two steps, no new crossouts appear. In general, one can forget about crossouts and start just circling all remaining numbers once a number exceeding the square root of the maximal number we are interested in is circled (in our example it is $5>\sqrt{20}$). The reason is that if a number $n$ is composite, then it has a prime divisor not exceeding $\sqrt n$.


Related Links

See also

Invalid username
Login to AoPS