Table of Contents

PNCX

ALGORITHM: sieve of eratosthenes

variant: baseline soe

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

variant: sieve of eratosthenes with sqrt trick (soes)

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

timing

ChrisB's pnc2 runtimes

VerbalGnat48's pnc2 runtimes

Xavier's pnc2 runtimes

MrVengeance's pnc2 runtimes

Darkmoon's pnc2 runtimes

amelvil2's pnc2 runtimes

Blaize patricelli's pnc2 runtimes