Πρόγραμμα: gcd.c (25 μονάδες)
Μέγιστος κοινός διαιρέτης ονομάζεται ο μεγαλύτερος ακέραιος που διαιρεί δύο ή περισσότερους ακέραιους αριθμούς. Για παράδειγμα ο μέγιστος κοινός διαιρέτης του 42 και του 27 είναι το 3 (καθώς διαιρεί ακριβώς και το 42/3=14 και το 27/3=9). Γράψτε ένα πρόγραμμα που διαβάζει δύο θετικούς ακεραίους σε δεκαδική μορφή από την γραμμή εντολών και τυπώνει τον μέγιστο κοινό διαιρέτη. Παραδείγματα εκτέλεσης ακολουθούν:
$ gcc -o gcd gcd.c
$ ./gcd 42 27
Greatest common divisor of 42 and 27 is 3
$ ./gcd 42 -27
Numbers must be positive
$ ./gcd 54 24
Greatest common divisor of 54 and 24 is 6
$ ./gcd 9827345 9182767
Greatest common divisor of 9827345 and 9182767 is 11
$ ./gcd 782936492674398272 982137984792892
Greatest common divisor of 782936492674398272 and 982137984792892 is 4
$ ./gcd 260056890954482 23809214813964
Greatest common divisor of 260056890954482 and 23809214813964 is 2982734
Ο αλγόριθμος του Ευκλείδη (με υπόλοιπα, όχι με διαδοχικές αφαιρέσεις) τελειώνει σε λίγα βήματα ακόμα και για πολύ μεγάλους αριθμούς, ενώ η δοκιμή όλων των πιθανών διαιρετών όχι. Τα παραδείγματα χρειάζονται 64-bit ακέραιους: διαβάστε τα ορίσματα με strtoll/strtoull και ελέγξτε ότι είναι έγκυροι θετικοί αριθμοί που χωράνε στον τύπο.
Αριθμός στον οδηγό: Α6.16
(στο κεφάλαιο) ·
Μόνιμο αναγνωριστικό: exam-2023-fall-ex6-q1 ·
Σύνδεσμος: https://progintro.github.io/study/questions/exams/exam-2023-fall-ex6-q1.html ·
Markdown (GitHub)