Sieve of Eratosthenes
## Smalltalk

The Sieve of Eratosthenes is a simple algorithm that finds the prime numbers up to a given integer.

- Task

Implement the Sieve of Eratosthenes algorithm, with the only allowed optimization that the outer loop can stop at the square root of the limit, and the inner loop may start at the square of the prime just found.

That means especially that you shouldn't optimize by using pre-computed *wheels*, i.e. don't assume you need only to cross out odd numbers (wheel based on 2), numbers equal to 1 or 5 modulo 6 (wheel based on 2 and 3), or similar wheels based on low primes.

If there's an easy way to add such a wheel based optimization, implement it as an alternative version.

- Note

- It is important that the sieve algorithm be the actual algorithm used to find prime numbers for the task.

- Related tasks

- Emirp primes
- count in factors
- prime decomposition
- factors of an integer
- extensible prime generator
- primality by trial division
- factors of a Mersenne number
- trial factoring of a Mersenne number
- partition an integer X into N primes
- sequence of primes by Trial Division

A simple implementation that you can run in a workspace. It finds all the prime numbers up to and including *limit*—for the sake of example, up to and including 100.

| potentialPrimes limit |

limit := 100.

potentialPrimes := Array new: limit.

potentialPrimes atAllPut: true.

2 to: limit sqrt do: [:testNumber |

(potentialPrimes at: testNumber) ifTrue: [

(testNumber * 2) to: limit by: testNumber do: [:nonPrime |

potentialPrimes at: nonPrime put: false

]

]

].

2 to: limit do: [:testNumber |

(potentialPrimes at: testNumber) ifTrue: [

Transcript show: testNumber asString; cr

]

]

This article is contributed by Priya and text available under CC-SA-4.0