Sieve of Eratosthenes

From Fōrmulæ wiki
Jump to: navigation, search

This page is the answer to the task Sieve of Eratosthenes in the Rosetta Code.

Description (from Rosetta Code)

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.

Program

The same program when the flowchart package visualization is selected. Click/tap to enlarge

SieveEratosthenesProgram1.png

Output

SieveEratosthenesOutput1.png