Výpočet a získání největšího společného dělitele a nejmenšího společného násobku v jazyce Python

Podnikání

Následuje popis výpočtu a získání největšího společného dělitele a nejmenšího společného násobku v jazyce Python.

  • Největší společný dělitel a nejmenší společný násobek dvou celých čísel
  • Největší společný dělitel a nejmenší společný násobek tří nebo více celých čísel

Všimněte si, že specifikace funkcí poskytovaných ve standardní knihovně se liší v závislosti na verzi jazyka Python. V tomto článku je také uveden příklad implementace funkce, která není ve standardní knihovně.

  • Python 3.4 nebo starší
    • GCD:fractions.gcd()(pouze dva argumenty)
  • Python 3.5 nebo novější
    • GCD:math.gcd()(pouze dva argumenty)
  • Python 3.9 nebo novější
    • GCD:math.gcd()(podporuje více než tři argumenty)
    • nejmenší společný jmenovatel:math.lcm()(podporuje více než tři argumenty)

Zde vysvětlíme metodu pomocí standardní knihovny Pythonu; NumPy lze snadno použít k výpočtu největšího společného dělitele a nejmenšího společného násobku pro každý prvek více polí.

Největší společný dělitel a nejmenší společný násobek dvou celých čísel

GCD

Od verze Python 3.5 je v matematickém modulu funkce gcd(). gcd() je zkratka pro

  • greatest common divisor

Vrací největší společný dělitel celého čísla zadaného v argumentu.

import math

print(math.gcd(6, 4))
# 2

Všimněte si, že v Pythonu 3.4 a dřívějších verzích je funkce gcd() v modulu fractions, nikoli v modulu math. fractions musí být importována a fractions.gcd().

nejmenší společný jmenovatel

Funkce lcm(), která vrací nejmenší společný násobek, byla přidána do matematického modulu v jazyce Python 3.9. lcm je zkratka slov

  • least common multiple

Vrátí nejmenší společný násobek celého čísla zadaného v argumentu.

print(math.lcm(6, 4))
# 12

Před verzí Python 3.8 není funkce lcm() k dispozici, ale lze ji snadno vypočítat pomocí funkce gcd().

lcm(a, b) = a * b / gcd(a, b)

Příklad implementace.

def my_lcm(x, y):
    return (x * y) // math.gcd(x, y)

print(my_lcm(6, 4))
# 12

/Protože výsledkem je desetinné číslo, použijí se dvě zpětná lomítka, aby se desetinná tečka zkrátila a vrátil se celočíselný výsledek dělení. Všimněte si, že se neprovádí žádné zpracování, aby se zjistilo, zda je argument celé číslo, nebo ne.

Největší společný dělitel a nejmenší společný násobek tří nebo více celých čísel

Python 3.9 nebo novější

Počínaje verzí Python 3.9 podporují všechny následující funkce více než tři argumenty.

  • math.gcd()
  • math.lcm()
print(math.gcd(27, 18, 9))
# 9

print(math.gcd(27, 18, 9, 3))
# 3

print(math.lcm(27, 9, 3))
# 27

print(math.lcm(27, 18, 9, 3))
# 54

*Pokud chcete vypočítat největšího společného dělitele nebo nejmenší společný násobek prvků seznamu, zadejte argument pomocí tohoto.

l = [27, 18, 9, 3]
print(math.gcd(*l))
# 3

print(math.lcm(*l))
# 54

Python 3.8 nebo starší

Před verzí 3.8 podporovala funkce gcd() pouze dva argumenty.

K nalezení největšího společného dělitele nebo nejmenšího společného násobku tří nebo více celých čísel není zapotřebí žádný zvlášť složitý algoritmus; stačí vypočítat největší společný dělitel nebo nejmenší společný násobek pro každou z násobných hodnot postupně pomocí funkce vyššího řádu reduce().

GCD

from functools import reduce

def my_gcd(*numbers):
    return reduce(math.gcd, numbers)

print(my_gcd(27, 18, 9))
# 9

print(my_gcd(27, 18, 9, 3))
# 3

l = [27, 18, 9, 3]
print(my_gcd(*l))
# 3

Opět upozorňujeme, že před verzí Pythonu 3.4 se funkce gcd() nacházela v modulu fraction, nikoli v modulu math.

nejmenší společný jmenovatel

def my_lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def my_lcm(*numbers):
    return reduce(my_lcm_base, numbers, 1)

print(my_lcm(27, 9, 3))
# 27

print(my_lcm(27, 18, 9, 3))
# 54

l = [27, 18, 9, 3]
print(my_lcm(*l))
# 54