Extra opdrachten met priemgetallen

Op deze pagina vind je de opdrachten die Roy en Harry op vrijdag 9 juni 2017 in een live-programmeerles hebben gedemonstreerd.

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:

Maak een gesorteerde lijst van alle getallen van 2 tot een zelf te kiezen maximum.
Kies het kleinste getal uit de lijst.
Streep alle veelvouden van het gekozen getal door (maar niet het getal zelf).
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.

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

Bron: Wikipedia

Opdracht 1

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.

Opdracht 2

Gegeven is een functie isPrime die bepaalt of een als input argument meegegeven integer een priemgetal is of niet. Het resultaat (een boolean) wordt teruggegeven via de returnwaarde van de functie. De flowchart van dit programma kun je hier downloaden en staat hieronder afgebeeld. Het bijbehorende C-programma kun je hier downloaden en staat hieronder afgebeeld.

Schrijf nu een functie met een input parameter n (een geheel getal groter dan 2) en twee output parameters: het kleinste priemgetal groter dan n en het grootste priemgetal kleiner dan n.
Schrijf ook een programma om de functie te testen.

Flowchart van functie isPrime

Flowchart van testprogramma voor functie isPrime

#!C
#include <stdio.h>
#include <stdbool.h>
#include <math.h>

bool isPrime(int n)
{
    if (n < 2)
    {
        return false;
    }
    for (int i = 2; i <= sqrt(n); i++)
    {
        if (n % i == 0)
        {
            return false;
        }
    }
    return true;
}

int main(void)
{
    int number;
    printf("Geef een geheel number: ");
    scanf("%d", &number);
    printf("Het number %d is ", number);
    if (isPrime(number) == true)
    {
        printf("een ");
    }
    else
    {
        printf("geen ");
    }
    printf("priemgetal\n");
    return 0;
}

Uitwerking opdracht 1

We zijn begonnen met een flowchart waarmee de functie zeef getest kan worden.

Flowchart van testprogramma voor functie zeef

Vervolgens hebben we een flowchart gemaakt van de functie zeef.

Flowchart van functie zeef

De Flowgorithm code kun je hier downloaden.

Vervolgens hebben we het C-programma geïmplementeerd en de versnellende maatregelen doorgevoerd. De code kun je hier downloaden.

#!C
#include <stdio.h>
#include <stdbool.h>
#include <math.h>

void zeef(bool b[], int n)
{
    b[0] = false;
    b[1] = false;
    //for (int i = 2; i < n; i++)
    // Versnelling 3:
    for (int 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 (int streep = 2 * i; streep < n; streep = streep + i)
            {
                b[streep] = false;
            }
        }
    }
}

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

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

int main(void)
{
    bool isPriem[1000];
    int n = sizeof isPriem / sizeof isPriem[0];
    initBoolArray(isPriem, n, true);
    zeef(isPriem, n);
    printf("Alle priemgetallen < %d:\n", n);
    printBoolArrayTrueIndexes(isPriem, n);
    printf("\n");
    return 0;
}

Uitwerking opdracht 2

Het onderstaande C-programma kun je hier downloaden.

#!C
#include <stdio.h>
#include <stdbool.h>
#include <math.h>

bool isPrime(int n)
{
    if (n < 2)
    {
        return false;
    }
    for (int i = 2; i <= sqrt(n); i++)
    {
        if (n % i == 0)
        {
            return false;
        }
    }
    return true;
}

void primesAround(int n, int *p_lower, int *p_higher)
{
    if (n > 2)
    {
        int lower = n;
        do
        {
            lower = lower - 1;
        } while (isPrime(lower) == false);
        {
        }
        int higher = n;
        do
        {
            higher = higher + 1;
        } while (isPrime(higher) == false);
        *p_lower = lower;
        *p_higher = higher;
    }
}

int main(void)
{
    int number;
    printf("Geef een geheel number > 2: ");
    scanf("%d", &number);
    int low, high;
    primesAround(number, &low, &high);
    printf("Het grootste priemgetal kleiner dan %d is %d.\n", number, low);
    printf("Het kleinste priemgetal groter dan %d is %d.\n", number, high);
    return 0;
}