Überlauf der Antwort für größere Werte

Question

Ich versuche, das LCM einer Zahl mit der folgenden Formel zu finden. Lcm = Gcd/(a ​​* b). Dies funktioniert gut für kleine Zahlen, aber für größere Zahlen, wie im Code gezeigt, überläuft es. Ich habe versucht, long long als variablen Typ zu verwenden, aber immer noch keinen Effekt. Wie behebe ich das Überlaufproblem?

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

long long int LCM(int n1, int n2){ 

    const int size = 2; 
    long long int sum; 
    long long int gcd; 
    long long int lcm = 0; 
    vector<int> number(2); 
    number[0] = n1; 
    number[1] = n2; 

while (true) 
{ 
    sum = number[0] % number[1]; 
    gcd = number[1]; 
    if (sum == 0) 
     break; 
    number[0] = number[1]; 
    number[1] = sum; 
} 

lcm = ((n1*n2)/gcd); 
return lcm; 
} 

int main() 
{ 

    cout << LCM(28851538, 1183019) << endl; 
    system("pause"); 

} 

Answer 1

Es gibt eine triviale Verbesserung.

Sie berechnen (n1 * n2)/gcd. Das wird überlaufen, wenn n1 * n2 zu groß ist, um in einen int zu passen. Eine offensichtliche Änderung wäre die Berechnung von ((lang lang) n1 * (lang lang) n2)/gcd. Das ist in Ordnung, solange n1 * n2 nicht zu groß ist, um in long long zu passen.

Aber angenommen, Sie möchten diese Funktion mit langen langen Argumenten verwenden. Denken Sie daran, dass gcd der größte gemeinsame Teiler von n1 und n2 ist. Es ist also ein Teiler von n1 und ein Teiler von n2. Also berechnen Sie (n1/gcd) * n2 oder (n2/gcd) * n1, was zum selben Ergebnis führt. Es wird keinen Überlauf geben, wenn das Endergebnis nicht zu groß ist.

lcm = n1*(n2/gcd); 

Answer 2

Da Sie wissen, dass gcd beiden Zahlen gleichmäßig in aufteilt, einfach die Reihenfolge der Operationen ändern !

vector<int> number(2) 

warum int wieder?

lcm = ((n1*n2)/gcd) 

Verwendung n1/gcd * n2

Answer 3

long long int LCM(int n1, int n2) 

Parameter sind int:

So einfach die Return-Anweisung ändern, um

return (n1/gcd) * n2;