Eπίλυση του προβλήματος 7 του Project Euler

Επίλυση του προβλήματος 7 του Project Euler

Στο παρόν άρθρο, θα εξετάσουμε την επίλυση του έβδομου προβλήματος του Project Euler, το οποίο αφορά τον υπολογισμό του 10001ου πρώτου αριθμού.

Αλγόριθμος Επίλυσης

Για να επιλύσουμε το πρόβλημα, μπορούμε να χρησιμοποιήσουμε έναν αλγόριθμο που βασίζεται στον έλεγχο κατά πρώτο των αριθμών. Ξεκινάμε με έναν αριθμό 2 και συνεχίζουμε να αυξάνουμε τον αριθμό κατά 1 σε κάθε επανάληψη. Για κάθε αριθμό, ελέγχουμε αν είναι πρώτος. Αν είναι πρώτος, αυξάνουμε τον μετρητή και ελέγχουμε αν έχουμε φτάσει στον 10001ο πρώτο αριθμό. Αν έχουμε φτάσει, τότε εμφανίζουμε τον αριθμό και τερματίζουμε το πρόγραμμα. Αν δεν έχουμε φτάσει, συνεχίζουμε τον έλεγχο για τον επόμενο αριθμό.

Παρακάτω παρουσιάζεται ο κώδικας σε γλώσσα C που υλοποιεί τον παραπάνω αλγόριθμο:

#include <stdio.h>
#include <stdbool.h>

bool isPrime(int num) {
    if (num <= 1)
        return false;

    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0)
            return false;
    }

    return true;
}

int main() {
    int count = 0;
    int number = 2;

    while (count < 10001) {
        if (isPrime(number))
            count++;

        if (count == 10001) {
            printf("Ο 10001ος πρώτος αριθμός είναι: %d\n", number);
            break;
        }

        number++;
    }

    return 0;
}
  

Με την εφαρμογή του παραπάνω αλγορίθμου, καταφέρνουμε να επιλύσουμε το έβδομο πρόβλημα του Project Euler και να βρούμε τον 10001ο πρώτο αριθμό.