gcd = 1, когда нет общих чисел

Question

16 (который имеет простое разложение 2^4) и 27 (который имеет простое разложение 3^3) не имеют общих простых факторов. Тогда почему результат gcd(16, 27) == 1?

Я проверил с Python:

>>> from fractions import gcd
>>> gcd(16, 27)
1

Answer 1

Вероятно, вас смущает то, что числа 16 и 27 не имеют общих делителей, кроме 1. GCD определяется как наибольший общий делитель / фактор, который делит оба числа. И вы думаете о сопряжениях! Но ни 16, ни 27 не являются простыми, чтобы быть проверенными на совместное простое число, поскольку для простого условия сравниваются только простые числа!!! Как видите, факторы (делители) 16 равны 1,2,4,8,16. Аналогично, факторы (делители) 27 составляют 1,3,9,27.

16---> 1,2,4,8,16

27---> 1,3,9,27.

Итак, проверяя highest/greatest common factor(h/gcf) ИЛИ ЖЕ greatest common divisor(gcd) из обоих чисел мы находим gcd равным 1.

Следовательно, ваш скрипт на python дает вам правильный результат, так как на самом деле gcd из 16 и 27 оказывается равным 1, как я объяснил выше!