Lab46 Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
======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:

<code>
    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
</code>

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:

<code>
    2  3     5     7     9  
11    13    15    17    19  
21    23    25    27    29  
31    33    35    37    39  
</code>

Then, you go to the next number: 3. Now you know 3 is a prime number, so you can remove multiples of 3:

<code>
    2  3     5     7        
11    13          17    19  
      23    25          29  
31          35    37        
</code>

You go through the entire list, and when you get to the end, you are only left with prime numbers:

<code>
    2  3     5     7        
11    13          17    19  
      23                29  
31                37        
</code>

<code>
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
</code>

====variant: sieve of eratosthenes with sqrt trick (soes)====

<code>
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
</code>
=====timing=====

====ChrisB's pnc2 runtimes====
{{ :notes:fall2024:projects:cbpnc2.png?600 |}}

====VerbalGnat48's pnc2 runtimes====
{{ :notes:fall2024:projects:carter_pnc2.png?600 |}}
====Xavier's pnc2 runtimes====
{{ :notes:fall2024:projects:xavierspnc2.png?600 |}}

====MrVengeance's pnc2 runtimes====
{{ :notes:fall2024:projects:pnc2-graph.png?600 |}}
====Darkmoon's pnc2 runtimes====
{{ :notes:fall2024:projects:cgrant9_pnc2.png?600 |}}

====amelvil2's pnc2 runtimes====
<dataplot center linespoints smooth 600x400 xlabel="range" ylabel="time (s)">
8192 0.083333 0.033333 0.033333
16384 0.25 0.05 0.05
32768 0.633333 0.116667 0.133333
65536 1.633333 0.25 0.233333
</dataplot>

====Blaize patricelli's pnc2 runtimes====
<dataplot center linespoints smooth 600x400 xlabel="range" ylabel="time (s)">
8192 0.03333 0.03333 0.01667
16384 0.1 0.08333 0.03333
32768 0.28333 0.13333 0.08333
65536 0.71667 0.28333 0.18333
</dataplot>
Lab46 Wiki

User Tools

Site Tools

Page Tools
