Sieve of Eratosthenes
Description:
Sieve of Eratosthenes
Theoretical introduction
The sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the multiples of 2.
Wikipedia, Sieve of Eratosthenes
Description of the algorithm
The multiples of a given prime are generated as a sequence of numbers starting from that prime, with constant difference between them that is equal to that prime.[1] This is the sieve's key distinction from using trial division to sequentially test each candidate number for divisibility by each prime.[2]
Wikipedia, Sieve of Eratosthenes
A visual representation:
(Source is Wikimedia Commons, Sieve_of_Eratosthenes_animation)
Problem description
Create a program that is able to calculate all the prime numbers up to a higher bound.
Given that:
The sieve of Eratosthenes is one of the most efficient ways to find all of the smaller primes
Wikipedia, Sieve of Eratosthenes
Samples
primes 5: 2, 3, 5
primes 10: 2, 3, 5, 7
Similar Kata:
Stats:
| Created | Sep 9, 2015 |
| Published | Sep 9, 2015 |
| Warriors Trained | 419 |
| Total Skips | 11 |
| Total Code Submissions | 644 |
| Total Times Completed | 221 |
| Haskell Completions | 103 |
| Java Completions | 120 |
| Total Stars | 11 |
| % of votes with a positive feedback rating | 87% of 79 |
| Total "Very Satisfied" Votes | 62 |
| Total "Somewhat Satisfied" Votes | 13 |
| Total "Not Satisfied" Votes | 4 |
| Total Rank Assessments | 13 |
| Average Assessed Rank | 6 kyu |
| Highest Assessed Rank | 4 kyu |
| Lowest Assessed Rank | 8 kyu |
