The sieve of Eratosthenes is one of the best algorithms for finding prime numbers, you may have noticed that up to this point all the code we have written has a complexity of O(n^2). The soe takes the next step and goes to O(nlog(log(n)).
Here is how the Sieve of Eratosthenes works:
First, you start with 2, and count up to your upper bound. For this example, let's say it is 40:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
Then, you go through the list and remove multiples of 2. After that, you go to the next remaining number, which you now know is prime. Then, you remove multiples of that number, and so on.
To continue from above, 2 is a prime number, so you leave it alone, and remove any multiples of 2:
2 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39
Then, you go to the next number: 3. Now you know 3 is a prime number, so you can remove multiples of 3:
2 3 5 7 11 13 17 19 23 25 29 31 35 37
You go through the entire list, and when you get to the end, you are only left with prime numbers:
2 3 5 7 11 13 17 19 23 29 31 37
START TIMEKEEPING NUMBER: FROM 2 THROUGH UPPERBOUND: SHOULD THE NUMBER SLOT BE TRUE: VALUE AT NUMBER IS PRIME, INCREMENT TALLY MULTIPLE: FROM NUMBER+NUMBER THROUGH UPPERBOUND: VALUE AT MULTIPLE IS NOT PRIME MULTIPLE IS MULTIPLE PLUS NUMBER PROCEED TO NEXT MULTIPLE INCREMENT NUMBER PROCEED TO NEXT NUMBER STOP TIMEKEEPING
START TIMEKEEPING NUMBER: FROM 2 THROUGH NUMBER*NUMBER<UPPERBOUND: SHOULD THE NUMBER SLOT BE TRUE: VALUE AT NUMBER IS PRIME, INCREMENT TALLY MULTIPLE: FROM NUMBER*NUMBER THROUGH UPPERBOUND: VALUE AT MULTIPLE IS NOT PRIME MULTIPLE IS MULTIPLE PLUS NUMBER PROCEED TO NEXT MULTIPLE INCREMENT NUMBER PROCEED TO NEXT NUMBER STOP TIMEKEEPING