Переполнение ответа для больших значений

Question

Я пытаюсь найти LCM числа, используя следующую формулу. Lcm = Gcd/(a ​​* b). Это работает отлично для небольшого числа, однако для больших чисел оно переполняется, как показано в коде. Я пробовал использовать длинный длинный тип переменной, но все равно никакого эффекта. Как устранить проблему переполнения?

#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

Существует тривиальное улучшение.

Вы вычисляете (n1 * n2)/gcd. Это будет переполнение, если n1 * n2 слишком велико, чтобы вписаться в int. Одним из очевидных изменений было бы вычисление ((длинный длинный) n1 * (длинный длинный) n2)/gcd. Это прекрасно, пока n1 * n2 не слишком большой, чтобы вписаться в длинный длинный.

Но предположим, что вы хотите использовать эту функцию с длинными длинными аргументами. Тогда помните, что gcd - наибольший общий делитель n1 и n2. Таким образом, это делитель n1 и делитель n2. Итак, вы вычисляете (n1/gcd) * n2 или (n2/gcd) * n1, что даст тот же результат. Не будет переполнения, если конечный результат слишком велик.

Так просто изменить оператор возврата к

return (n1/gcd) * n2; 

Answer 2

Поскольку вы знаете, что gcd делится равномерно на оба номера, просто изменить порядок операций:

lcm = n1*(n2/gcd); 

Answer 3

long long int LCM(int n1, int n2) 

параметры являются ИНТ !

vector<int> number(2) 

Почему int снова?

lcm = ((n1*n2)/gcd) 

использование n1/НОД * n2