Πρόβλημα 5/ Project Euler

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

Στο παρόν άρθρο, θα εξετάσουμε την επίλυση του πέμπτου προβλήματος του Project Euler, ένα πρόβλημα που αφορά τον ελάχιστο κοινό πολλαπλάσιο (ΕΚΠ) των αριθμών από 1 έως και έναν δοθέντα αριθμό.

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

Για να επιλύσουμε το πρόβλημα, μπορούμε να χρησιμοποιήσουμε τον αλγόριθμο του "Σημαίνει και Κυρίαρχος", όπου κάνουμε χρήση του γεγονότος ότι το ΕΚΠ δύο αριθμών μπορεί να υπολογιστεί με βάση τον αλγόριθμο του Μέγιστου Κοινού Διαιρέτη.

Ακολουθούμε τα εξής βήματα:

1. Αρχικοποιούμε μια μεταβλητή smallestMultiple με την τιμή 1, η οποία θα αποθηκεύει το ελάχιστο κοινό πολλαπλάσιο.
2. Ξεκινάμε έναν βρόχο επανάληψης από το 1 έως τον δοθέντα αριθμό.
3. Ελέγχουμε αν ο τρέχον αριθμός διαιρείται ακριβώς με το ελάχιστο κοινό πολλαπλάσιο. Αν όχι, προχωράμε στο επόμενο βήμα.
4. Χρησιμοποιούμε τον αλγόριθμο του Μέγιστου Κοινού Διαιρέτη για να υπολογίσουμε τον νέο ελάχιστο κοινό πολλαπλάσιο με βάση τον τρέχοντα αριθμό και το ελάχιστο κοινό πολλαπλάσιο.

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

#include <stdio.h>

int findSmallestMultiple(int n) {
    int smallestMultiple = 1;

    for (int i = 1; i <= n; i++) {
        if (smallestMultiple % i != 0) {
            // Υπολογισμός Μέγιστου Κοινού Διαιρέτη
            int j = i;
            int k = smallestMultiple;
            while (k != 0) {
                int temp = k;
                k = j % k;
                j = temp;
            }

            smallestMultiple *= i / j;
        }
    }

    return smallestMultiple;
}

int main() {
    int n = 20;
    int smallestMultiple = findSmallestMultiple(n);

    printf("Το ελάχιστο κοινό πολλαπλάσιο των αριθμών από 1 έως %d είναι: %d\n", n, smallestMultiple);

    return 0;
}
  

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