priemgetallen

Opdracht 3.1.5

Op deze pagina vind je een mogelijke uitwerking van opdracht 3.1.5 van EMS2.

Priemgetallen

Een priemgetal is een natuurlijk getal groter dan 1 dat slechts twee natuurlijke getallen als deler heeft, namelijk 1 en zichzelf. De zeef van Eratosthenes (bibliothecaris van Alexandrië vanaf ca. 240 v.Chr.) is een al zeer lang bekend algoritme om priemgetallen te vinden.

Methode:

1. Maak een gesorteerde lijst van alle getallen van 2 tot een zelf te kiezen maximum.
2. Kies het kleinste getal uit de lijst.
3. Streep alle veelvouden van het gekozen getal door (maar niet het getal zelf).
4. Kies het volgende getal uit de lijst en ga verder met stap 3. De getallen die op deze manier overblijven zijn alle priemgetallen tot het maximum.

De procedure kan op enkele manieren versneld worden.

1. Het heeft geen zin in stap 4 een getal te kiezen dat al doorgestreept is, want alle veelvouden daarvan zijn al doorstreept.
2. Men kan met doorstrepen beginnen met het kwadraat van het gekozen getal. Alle kleinere veelvouden zijn al doorstreept.
3. Is het gekozen getal groter dan de wortel uit het maximum, dan is de procedure voltooid.

Bron: Wikipedia

Opdracht 3.1.5

Schrijf een functie die in een array met n booleaanse variabelen voor elke index aangeeft of deze index een priemgetal is. Maak daarbij gebruik van de zeef van Erastothenes (zonder versnellende maatregelen).

• Maak eerst een flowchart.
• Implementeer je flowchart in C.
• Schrijf ook een programma om de functie te testen.
• Maak het programma zo snel mogelijk door de hierboven beschreven versnellende maatregelen toe te passen.

Uitwerking opdracht 3.1.5

Een flowchart van het programma main waarmee de functie zeef getest kan worden is hieronder gegeven.

De flowchart voor de functie zeef is hieronder gegeven.

Het C-programma dat de bovenstaande flowcharts implementeert en waarbij de versnellende maatregelen zijn doorgevoerd kun je hieronder vinden. De code kun je hier downloaden.

/*
 * Copyright (C) 2026, Hogeschool Rotterdam
 * All rights reserved.
 */

#include <fsl_debug_console.h>
#include <stdbool.h>
#include <math.h>
void BOARD_InitHardware(void);

void zeef(bool b[], size_t n)
{
    b[0] = false;
    b[1] = false;
    //for (size_t i = 2; i < n; i++)
    // Versnelling 3:
    for (size_t i = 2; i <= sqrt(n); i++)
    {
        // Versnelling 1:
        if (b[i] == true)
        {
            //for (int streep = 2 * i; streep < n; streep = streep + i)
            // Versnelling 2:
            for (size_t streep = 2 * i; streep < n; streep = streep + i)
            {
                b[streep] = false;
            }
        }
    }
}

void initBoolArray(bool a[], size_t n, bool init)
{
    for (size_t i = 0; i < n; i++)
    {
        a[i] = init;
    }
}

void printBoolArrayTrueIndexes(bool a[], size_t n)
{
    int teller = 0;
    for (size_t i = 0; i < n; i++)
    {
        if (a[i] == true)
        {
            PRINTF("%d ", i);
            teller++;
            if (teller == 10)
            {
                PRINTF("\n");
                teller = 0;
            }
        }
    }
}

int main(void)
{
    BOARD_InitHardware();
    
    bool isPriem[1000];
    size_t n = sizeof isPriem / sizeof isPriem[0];
    initBoolArray(isPriem, n, true);
    zeef(isPriem, n);
    PRINTF("Alle priemgetallen < %d:\n", n);
    printBoolArrayTrueIndexes(isPriem, n);
    PRINTF("\n");
    
    // Wacht tot debugger afgesloten wordt
    while (1);
    return 0;
}