Sieve Of Eratosthenes You are currently not logged in Click here to log in

List of All Pages Recent Changes Random Pages Links to this page Edit this page Search Entry portal Advice For New Users

Navigation

SEARCH

Front Page

New User Introduction

Contact Us

Creating Pages

Axiom Of Choice

Eratosthenes, an ancient Greek Mathematician, developed a simple algorithm for finding prime numbers less than a desired number.

• Draw a table of all numbers less than the desired number n
• Draw a circle around the number 2
• Square 2 giving 4, then starting at 4, cross out every second number

• Circle the next number not crossed out (this is a prime number) and call it "p"
• Square p, giving $p^2$ and starting from there, cross out every $p^{th}$ number

• Repeat the last step until the square is larger than n

All the remaining uncrossed numbers are also prime numbers.

Note that this procedure does not use division.

---

(none)		(none)				(none)
↓		↓		↓		↓
Eratosthenes				(none)
				↓
			⇌	You are here SieveOfEratosthenes
				↓
				PrimeNumber
↓		↓		↓		↓
FamousPeople		(none)				CompositeNumber CountingNumber Divisor PrimePair WholeNumber

---

Local neighbourhood - D3

---

Last change to this page Full Page history Links to this page

Edit this page   (with sufficient authority) Change password

Recent changes All pages Search