Неверный результат деления произведения двух целых чисел на их gcd

Question

Мы знаем, что для двух чисел «а» и «б»;произведение a & b равно произведению GCD (a, b) и LCM (a, b).

Итак, чтобы найти LCM из двух чисел, я написал этот алгоритм на Python:

def gcd(a,b):

  if b==0:
     return a
  else:
     a_rem = a%b
     return gcd(b,a_rem)

print(int(a*b/(gcd(a,b)))

Теперь, проверяя различные тестовые случаи, я обнаружил это:

Ввод: 226553150 1023473145

Мой вывод: 46374212988031352

Правильный вывод: 46374212988031350

Я не могу выяснить, почему это происходит, по какой-то причине неверна только последняя цифра !!

Answer 1

В вашем случае это вывод на каждом шаге GCD

1023473145 226553150
226553150 117260545
117260545 109292605
109292605 7967940
7967940 5709385 *1005* 570938
2258555 1192275
1192275 1066280
1066280 125995
125995 58320
58320 9355
9355 2190
2190 595
595 405
405 190
190 25
25 15
15 10
10 5
5 0

, который дает GCD как 5, который используется для деления a * b и, по существу, преобразования float в int какВ результате разница.

Answer 2

Чтобы избежать потери точности из-за целочисленного преобразования, используйте целочисленное деление // вместо деления с плавающей точкой /:

print(a*b//gcd(a,b))  # prints 46374212988031350

Небольшая оптимизация: так как каждый из a иb делится на их gcd, делим перед умножением, поэтому размер целых чисел меньше.

print(a*(b//gcd(a,b)))  # prints 46374212988031350

Дальнейшая оптимизация: в Python 3.5+ gcd встроен в , поэтому используйте from math import gcdвместо того, чтобы реализовать это самостоятельно.

Answer 3

Похоже, вы используете Python3.Деление '/' выполняет вычисление числа с плавающей запятой и возвращает результат в виде числа с плавающей запятой, что не является точным для большого числа.Это не относится к вашей функции gcd.Вы потеряете больше цифр точности, если сделаете деление с еще большими числами.Попробуйте int (12345678923456789123456789/1)