Difference between revisions of "Sieve of Eratosthenes"

(took out a section-see discussion page)
Line 1: Line 1:
 
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!
 
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!
===Example===
+
 
''It would be nice to really run the sieve up to 15 or 20; unfortunately, I could not find any good way to represent circled and crossed out numbers; italic and bold styles are not distinctive enough and to create crossed numbers in LaTeX is a headache. Maybe somebody else has an idea how to do it...''
 
 
===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]

Revision as of 15:57, 19 June 2006

The Sieve of Eratosthenes is a simple method to quickly uncover a short list of primes. Begin by writing positive numbers starting with $2$ 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!

Related Links

Website with good visual example

Invalid username
Login to AoPS