least common multiple

least common multiple (tsz. least common multiples)

1. (informatika) legkisebb közös többszörös

• lowest common multiple
• smallest common multiple

Az LCM (Least Common Multiple) vagyis legkisebb közös többszörös egy matematikai fogalom, amely két vagy több szám legkisebb olyan többszörösét jelenti, amely mindegyik szám osztója. Például a 4 és 6 esetén a legkisebb közös többszörös 12, mivel 12 a legkisebb szám, amely osztható mind 4-gyel, mind 6-tal.

Az egyik legegyszerűbb, de nem túl hatékony módszer az, hogy megkeressük az első olyan számot, amely osztható mindkét adott számmal:

#include <iostream>
using namespace std;

int lcm_bruteforce(int a, int b) {
    int max_ab = max(a, b); 
    while (true) {
        if (max_ab % a == 0 && max_ab % b == 0)
            return max_ab;
        max_ab++;
    }
}

int main() {
    int a = 12, b = 18;
    cout << "LCM: " << lcm_bruteforce(a, b) << endl;
    return 0;
}

Ez a módszer kis számok esetén működik, de nagyobb számoknál lassú.

Hatékonyabb módszer az LCM meghatározására a legnagyobb közös osztó (GCD, Greatest Common Divisor) használata. Az összefüggés a következő:

$${\displaystyle {\text{LCM}}(a,b)={\frac {|a\times b|}{{\text{GCD}}(a,b)}}}$$

Ehhez szükségünk van egy hatékony GCD algoritmusra, például az Euklideszi algoritmusra:

#include <iostream>
using namespace std;

// Euklideszi algoritmus a legnagyobb közös osztóhoz (GCD)
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// LCM kiszámítása a GCD segítségével
int lcm(int a, int b) {
    return (a / gcd(a, b)) * b; // A szorzás előtt osztunk a túlcsordulás elkerülése miatt
}

int main() {
    int a = 12, b = 18;
    cout << "LCM: " << lcm(a, b) << endl;
    return 0;
}

Ez a módszer hatékony, mivel az Euklideszi algoritmus időbonyolultsága O(log min(a, b)), így gyorsan működik nagyobb számok esetén is.

Ha több szám esetén akarunk LCM-et számolni, akkor páronként haladhatunk a következő módon:

#include <iostream>
#include <vector>
using namespace std;

// GCD meghatározása
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

// LCM meghatározása
int lcm(int a, int b) {
    return (a / gcd(a, b)) * b;
}

// Több szám LCM-je
int lcm_multiple(const vector<int>& numbers) {
    int result = numbers;
    for (size_t i = 1; i < numbers.size(); i++) {
        result = lcm(result, numbers);
    }
    return result;
}

int main() {
    vector<int> nums = {12, 18, 24, 30};
    cout << "LCM of multiple numbers: " << lcm_multiple(nums) << endl;
    return 0;
}

Ez a módszer sorban kiszámolja az LCM-et a tömb elemeire.

1. Brute-force módszer: Egyszerű, de lassú, ha nagy számokkal dolgozunk.
2. GCD segítségével: Hatékony, és elkerüli a felesleges iterációkat.
3. Több szám esetén: Páronként alkalmazzuk az LCM-et.

Ezzel az algoritmussal gyorsan és hatékonyan kiszámíthatjuk az LCM-et C++ nyelven.

• least common multiple - Szótár.net (en-hu)
• least common multiple - Sztaki (en-hu)
• least common multiple - Merriam–Webster
• least common multiple - Cambridge
• least common multiple - WordNet
• least common multiple - Яндекс (en-ru)
• least common multiple - Google (en-hu)
• least common multiple - Wikidata
• least common multiple - Wikipédia (angol)