Least common multiple

1. Sablon:Matematika 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.

LCM kiszámítása C++ nyelven

1. Alapmódszer (brute-force)

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ú.

2. LCM a legnagyobb közös osztó (GCD) segítségével

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ő:

$$\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.

3. Több szám legkisebb közös többszöröse

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[0];
    for (size_t i = 1; i < numbers.size(); i++) {
        result = lcm(result, numbers[i]);
    }
    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.

---

Összegzés

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.