Υπολογιστής LCM - Λιγότερο Κοινό Πολλαπλάσιο

Τι είναι το LCM (Λιγότερο Κοινό Πολλαπλό);

ΤοΛιγότερο κοινό πολλαπλάσιο (LCM)είναι ο μικρότερος θετικός ακέραιος αριθμός που διαιρείται απόλυτα με κάθε έναν από αυτούς τους ακέραιους αριθμούς -- χωρίς να αφήνει υπόλοιπο.

Για παράδειγμα, σκεφτείτε τους αριθμούς 4 και 6.12Τα πολλαπλάσια του 6 είναι:12, 18, 24 ... Ο πρώτος αριθμός που εμφανίζεται και στους δύο καταλόγους είναι 12, έτσι LCM ((4, 6) = 12.

Η LCM είναι μια από τις πιο θεμελιώδεις έννοιες στη θεωρία των αριθμών και την αριθμητική.Μεγαλύτερος κοινός διαιρέτης (GCD), επίσης γνωστός ως ο Μεγαλύτερος Κοινός Παράγοντας (ΜΚΠ), μέσω της κομψής ταυτότητας:

LCM (α, β) = a x β / GCD (α, β)

Αυτή η σχέση μας επιτρέπει να υπολογίσουμε αποτελεσματικά το LCM χρησιμοποιώντας τον αλγόριθμο του Ευκλείδη για το GCD, ο οποίος τρέχει σε λογαριθμικό χρόνο ακόμα και για πολύ μεγάλους ακέραιους αριθμούς.

Η LCM ορίζεται μόνο για ακέραιους αριθμούς. Για δύο θετικούς ακέραιους αριθμούς, η LCM είναι πάντα τουλάχιστον τόσο μεγάλη όσο ο μεγαλύτερος από τους δύο αριθμούς και το πολύ ίση με το προϊόν τους.Συμπλήρωμα), τότε LCM ((a, b) = a x b.

Πώς Να Βρείτε Το LCM - Τρεις Μεθόδους Εξηγούνται

Η κατανόηση κάθε μεθόδου εμβαθύνει την αίσθηση των αριθμών και σας βοηθά να επιλέξετε την πιο αποτελεσματική προσέγγιση για ένα δεδομένο πρόβλημα.

Μέθοδος 1: Καταχώριση πολλαπλών

Γράψτε τα πολλαπλάσια κάθε αριθμού μέχρι να βρείτε το πρώτο που μοιράζονται.

Παράδειγμα: LCM ((6, 8)

• Πολλαπλάσια των 6: 6, 12, 18,24, 30 ...
• Πολλαπλάσια των 8: 8, 16,24, 32 ...
• LCM ((6, 8) =24

Μέθοδος 2: Πρώτη παραγοντοποίηση

Χώρισε κάθε αριθμό στους πρώτους συντελεστές του.μέγιστη ισχύςκάθε πρώτου αριθμού που εμφανίζεται σε οποιαδήποτε παραγοντοποίηση και πολλαπλασιάστε τα μαζί.

Παράδειγμα: LCM ((12, 18)

• 12 = 22 x 31
• 18 = 21 x 32
• Πάρτε τις υψηλότερες δυνάμεις: 22 x 32 = 4 x 9 =36
• LCM ((12, 18) =36

Μέθοδος 3: Χρήση GCD (Πιο Αποδοτική)

Εφαρμόστε τη φόρμουλαLCM (α, β) = (α x β) / GCD (α, β)Για να βρείτε το GCD, χρησιμοποιήστε τον αλγόριθμο του Ευκλείδη: αντικαταστήστε επανειλημμένα τον μεγαλύτερο αριθμό με το υπόλοιπο όταν διαιρείτε τον μεγαλύτερο με τον μικρότερο, μέχρι να φτάσετε στο 0.

Παράδειγμα: LCM ((48, 36)

• GCD ((48, 36): 48 = 1x36 + 12 -> GCD ((36, 12): 36 = 3x12 + 0 -> GCD = 12
• LCM ((48, 36) = (48 x 36) / 12 = 1728 / 12 =144

Πίνακας αναφοράς LCM - Κοινά ζεύγη αριθμών

Ο παρακάτω πίνακας δίνει τιμές LCM για τα συχνά χρησιμοποιούμενα ζεύγη αριθμών.

Παρατηρήστε το μοτίβο: όταν ένας αριθμός διαιρεί τον άλλο ομοιόμορφα (π.χ. 5 και 10), ο LCM είναι ο μεγαλύτερος αριθμός.

LCM τριών ή περισσότερων αριθμών

Για να βρείτε το LCM τριών ή περισσότερων αριθμών, εφαρμόστε την συσχετιστική ιδιότητα του LCM επανάληπτα:

Δοκιμαστική μονάδα

Μπορείτε να το επεκτείνετε σε οποιοδήποτε αριθμό ακέραιων αριθμών.

LCM ((4, 6, 10)

1. LCM ((4, 6) = 12
2. LCM ((12, 10) = 60
3. LCM ((4, 6, 10) =60

Εναλλακτικά, χρησιμοποιήστε την παραγοντοποίηση πρώτων σε όλους τους αριθμούς ταυτόχρονα:

• 4 = 22
• 6 = 21 x 31
• 10 = 21 x 51
• LCM = 22 x 31 x 51 = 4 x 3 x 5 =60

Πραγματικές εφαρμογές του LCM

Το LCM μπορεί να μοιάζει με μια αφηρημένη μαθηματική έννοια, αλλά εμφανίζεται σε πολλά πρακτικά σενάρια στην καθημερινή ζωή, τη μηχανική και τον προγραμματισμό.

Προσθήκη και αφαίρεση κλάσεων

Για να προσθέσετε κλάσματα με διαφορετικούς παρονομαστές, πρέπει πρώτα να βρείτε τοΕλάχιστος κοινός παρονομαστής (LCD)-- που είναι απλά το LCM των παρονομαστών.

Παράδειγμα: 1/4 + 1/6. LCD = LCM ((4, 6) = 12. Έτσι: 3/12 + 2/12 = 5/12.

Χωρίς LCM, η αριθμητική με κλάσματα απαιτεί εργασία με περιττούς μεγάλους αριθμούς.

Προγραμματισμός και συγχρονισμός

Το LCM σου λέει πότε τα κυκλικά γεγονότα θα συμπίπτουν.

• Χρονοδιάγραμμα λεωφορείων/αυτοκινήτων:Εάν το λεωφορείο Α αναχωρεί κάθε 12 λεπτά και το λεωφορείο Β κάθε 8 λεπτά, συμπίπτουν κάθε LCM ((12, 8) = 24 λεπτά.
• Συστήματα εργαλείων:Ένα εργαλείο με 12 δόντια που συνδέεται με ένα εργαλείο με 8 δόντια επιστρέφει στην αρχική ευθυγράμμιση κάθε LCM ((12, 8) = 24 περιστροφές του μικρότερου εργαλείου.
• Μουσική και ρυθμός:Ένα μοτίβο ρυθμού 3 και ένα μοτίβο ρυθμού 4 ευθυγραμμίζουν κάθε LCM ((3, 4) = 12 ρυθμούς -- η βάση του πολυρύθμου στη μουσική.
• Φώτα που αναβοσβήνουν:Δύο φώτα κυκλοφορίας σε κύκλους 30 και 45 δευτερολέπτων θα είναι και τα δύο πράσινα ταυτόχρονα κάθε LCM ((30, 45) = 90 δευτερόλεπτα.

Κρυπτογραφία και Μονδρική Αριθμητική

Στην κρυπτογράφηση RSA, η συνάρτηση του Carmichael λ ((n) σχετίζεται με το LCM. Συγκεκριμένα, λ ((pq) = LCM ((p-1, q-1) για διακριτούς πρώτους αριθμούς p και q. Αυτή η τιμή LCM χρησιμοποιείται για τον υπολογισμό των εκθετών κρυπτογράφησης και αποκρυπτογράφησης στο RSA, καθιστώντας το LCM αναπόσπαστο μέρος της ασφάλειας του διαδικτύου.

Επιστήμη των υπολογιστών: ευθυγράμμιση μνήμης

Οι διευθύνσεις μνήμης του υπολογιστή πρέπει συχνά να ευθυγραμμίζονται με πολλαπλάσια ορισμένων μεγεθών λέξεων (π.χ. 4 bytes ή 8 bytes).

LCM vs GCD - Βασικές διαφορές

Η LCM και η GCD είναι συμπληρωματικές έννοιες που μαζί καταγράφουν την πολλαπλασιαστική δομή των ακέραιων αριθμών.

Η βασική ταυτότηταLCM ((a,b) x GCD ((a,b) = a x bΑυτό σημαίνει ότι γνωρίζοντας το ένα δίνετε αμέσως το άλλο αν γνωρίζετε τους αρχικούς αριθμούς.

Για παράδειγμα: LCM ((12, 18) = 36 και GCD ((12, 18) = 6. Ελέγξτε: 36 x 6 = 216 = 12 x 18.

Ειδικές περιπτώσεις και περιθωριακές συνθήκες

Η κατανόηση των οριακών περιπτώσεων του LCM βοηθά στην αποφυγή κοινών λαθών στους υπολογισμούς και τον προγραμματισμό.

• LCM ((n, n) = n:Οποιοσδήποτε αριθμός έχει τον εαυτό του ως LCM με τον εαυτό του.
• LCM(1, n) = n:Το 1 διαιρεί κάθε ακέραιο αριθμό, έτσι LCM(1, n) = n για κάθε θετικό ακέραιο αριθμό n.
• LCM διαδοχικών ακέραιων αριθμών:LCM (n, n+1) = n (n+1) επειδή οι διαδοχικοί ακέραιοι αριθμοί είναι πάντα συνπρώτοι (GCD = 1).
• LCM με πρώτους αριθμούς:Αν το p είναι πρώτος και το p δεν διαιρεί το n, τότε το LCM (p, n) = p x n. Αν το p διαιρεί το n, τότε το LCM (p, n) = n.
• LCM των δυνάμεων 2:LCM ((2, 4, 8, 16) = 16 -- η υψηλότερη δύναμη στο σύνολο.
• Αρνητικοί αριθμοί:Το LCM ορίζεται συνήθως για θετικούς ακέραιους αριθμούς. Για αρνητικές εισροές, χρησιμοποιήστε απόλυτες τιμές: LCM ((-4, 6) = LCM ((4, 6) = 12.
• Μηδέν:LCM(0, n) = 0 κατά σύμβαση (αφού το 0 είναι πολλαπλάσιο κάθε ακέραιου αριθμού).

LCM στα Μαθηματικά του Γυμνασίου

Το LCM εισάγεται στα μαθηματικά προγράμματα σπουδών στο δημοτικό και το γυμνάσιο, κυρίως στο πλαίσιο της αριθμητικής κλάσεων.

• Βαθμός 4 - 5:Πολλαπλάσια και συντελεστές· προσδιορισμός LCM με καταχώριση πολλαπλάσιων
• Βαθμός 5 - 6:Προσθήκη και αφαίρεση κλάσεων χρησιμοποιώντας LCD (= LCM των παρονομαστών)
• Βαθμοί 6 - 7:Μέθοδος πρώτων παραγόντων για το LCM· σχέση με το GCF
• Βαθμός 8+:ΛΚΜ σε αλγεβρικά κλάσματα, πολυωνυμική ΛΚΜ, εφαρμογές αρίθμησης

Μια κοινή τεχνική στην τάξη είναι η "μέθοδος σκάλας" (που ονομάζεται επίσης "μέθοδος τούρτας" ή "μέθοδος κουτιού"): διαιρέστε και τους δύο αριθμούς με κοινούς πρώτους παράγοντες ταυτόχρονα, συνεχίζοντας μέχρι οι υπόλοιποι αριθμοί να μην έχουν κοινούς παράγοντες, στη συνέχεια πολλαπλασιάστε όλους τους διαιρέτες και τους υπόλοιπους αριθμούς μαζί.

Παράδειγμα μεθόδου κλίμακας: LCM

2 ∙ 24 ∙ 36 ∙ 2 ∙ 12 ∙ 18 ∙ 3 ∙ 6 ∙ 9 ∙ 2 ∙ 3 LCM = 2 x 2 x 3 x 2 x 3 = 72

Επαληθεύστε: LCM ((24, 36) = (24 x 36) / GCD ((24, 36) = 864 / 12 = 72.

LCM στον προγραμματισμό και την ανάπτυξη λογισμικού

Το LCM εμφανίζεται συχνά σε εργασίες προγραμματισμού, από το σχεδιασμό αλγορίθμων μέχρι τον προγραμματισμό συστημάτων.

Αποτελεσματικός υπολογισμός LCM χρησιμοποιώντας GCD (Python):

from math import gcd

def lcm(a, b):
    return abs(a * b) // gcd(a, b)

# LCM of multiple numbers:
from functools import reduce
def lcm_multiple(*nums):
    return reduce(lcm, nums)

# Examples:
print(lcm(12, 18))        # 36
print(lcm_multiple(4, 6, 10))  # 60

Κοινές εφαρμογές προγραμματισμού:

• Προγραμματισμός εργασιών:Εάν μια εργασία στο παρασκήνιο Α εκτελείται κάθε 15 δευτερόλεπτα και η εργασία Β εκτελείται κάθε 20 δευτερόλεπτα, συμπίπτουν κάθε LCM ((15, 20) = 60 δευτερόλεπτα.
• Ευθυγράμμιση συστοιχίας:Κατά την ταυτόχρονη επεξεργασία πολλαπλών συστημάτων διαφορετικού μήκους (π.χ. ήχου σε 44,100 Hz και βίντεο σε 30 fps), η LCM των μήκων κύκλων τους καθορίζει πότε επανασυντονίζονται όλα τα ρεύματα.
• Δημιουργία κρυπτογραφικού κλειδιού:Στο RSA, λ ((n) = LCM ((p-1, q-1) είναι η οντότητα του Καρμάικλ -- που χρησιμοποιείται για να βρεθούν έγκυροι εκθέτες κρυπτογράφησης.
• Τμήματα με κωδικό:Γλώσσες όπως η Python (Fraction class) και η Java (BigInteger) χρησιμοποιούν LCM εσωτερικά για την αριθμητική κλάσεων, εξασφαλίζοντας ότι οι παρονομαστές παραμένουν όσο το δυνατόν μικρότεροι.

Στο Python 3.9+, το math.lcm() προστέθηκε στην τυποποιημένη βιβλιοθήκη, υποστηρίζοντας πολλαπλά επιχειρήματα: math.lcm(4, 6, 10) επιστρέφει 60.

Πρακτική LCM Προβλήματα με λύσεις

Δοκιμάστε την κατανόησή σας με τα παρακάτω προβλήματα πρακτικής, καθένα από τα οποία παρουσιάζει ένα διαφορετικό σενάριο όπου απαιτείται ο υπολογισμός LCM:

Για την επαλήθευση του προβλήματος 5: 720 ÷ 36 = 20 , 720 ÷ 48 = 15 , 720 ÷ 60 = 12 . Και τα τρία διαιρούνται ομοιόμορφα. Και το 720 είναι ο μικρότερος τέτοιος αριθμός (προσπαθήστε 360: 360 ÷ 48 = 7.5). Αυτοί οι τύποι προβλημάτων - προγραμματισμός, αριθμητική κλάσεων και συστήματα ταχυτήτων - αντιπροσωπεύουν τις τρεις πιο κοινές εφαρμογές LCM στον πραγματικό κόσμο που θα συναντήσετε.

Η μέθοδος GCD είναι αξιόπιστα η ταχύτερη προσέγγιση για οποιοδήποτε ζευγάρι ακέραιων, ανεξάρτητα από το μέγεθος. Μια τελική σημείωση σχετικά με την αποδοτικότητα: για πολύ μεγάλους αριθμούς (εκατοντάδες ψηφία), ακόμη και ο αλγόριθμος του Ευκλείδη χρησιμοποιεί την εκτεταμένη GCD ή δυαδική παραλλαγή GCD για την αποδοτικότητα. Τα math.gcd) και math.lcm) του Python χρησιμοποιούν βελτιστοποιημένες υλοποιήσεις C που χειρίζονται αυθαίρετα μεγάλα ακέραια, γι 'αυτό και ο ηλεκτρονικός υπολογιστής μας μπορεί επίσης να χειριστεί στιγμιαία μεγάλες εισροές χωρίς προβλήματα απόδοσης.