Какие знаешь примитивы GCD?

Примитивные типы данных в контексте GCD

В Python есть несколько примитивных типов, которые используются при вычислении наибольшего общего делителя (GCD):

Целые числа (int)

Основной примитивный тип для работы с GCD:

import math

# Встроенная функция
result = math.gcd(48, 18)  # 6

# Реализация алгоритма Евклида
def gcd(a: int, b: int) -> int:
    while b:
        a, b = b, a % b
    return a

print(gcd(48, 18))  # 6

Типы данных, поддерживаемые GCD

int — основной примитив:

• Неограниченная точность
• Поддержка отрицательных чисел
• Встроенная функция math.gcd() работает только с целыми числами

float — не поддерживается напрямую:

• math.gcd() выбросит TypeError
• Нужна предварительная конвертация

# Неправильно
math.gcd(5.5, 3.3)  # TypeError

# Правильно
from fractions import Fraction
f1 = Fraction(5.5).limit_denominator()
f2 = Fraction(3.3).limit_denominator()

bool — подтип int в Python:

math.gcd(True, False)  # 1 (True = 1, False = 0)
math.gcd(True, True)   # 1

Работа с несколькими числами (Python 3.9+)

from functools import reduce
import math

numbers = [48, 18, 24, 36]
result = reduce(math.gcd, numbers)  # 6

GCD для дробей

from fractions import Fraction

# GCD знаменателей и числителей
f1 = Fraction(6, 9)   # 2/3
f2 = Fraction(4, 12)  # 1/3

print(math.gcd(f1.numerator, f1.denominator))  # 3

Примитивные операции в алгоритме Евклида

Основные операции, которые работают с примитивами:

• Присваивание — присваивание переменным
• Деление по модулю — операция модуля (работает быстрее всего)
• Вычитание — альтернативный способ
• Сравнение — условие цикла

# Версия через вычитание
def gcd_subtraction(a: int, b: int) -> int:
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a
    return a

Асимптотическая сложность

• math.gcd() — O(log(min(a, b)))
• Реализация на C-уровне
• Оптимизирована для больших чисел

Вывод: примитивным типом для GCD в Python является int. Все остальные типы либо не поддерживаются, либо требуют предварительной конвертации.