Suurima ühise jagaja ja väikseima ühise kordaja arvutamine ja saamine Pythonis

Järgnevalt kirjeldatakse, kuidas Pythonis arvutada ja saada suurim ühine jagaja ja väikseim ühine korrutis.

• Kahe täisarvu suurim ühine jagaja ja väikseim ühine korrutis
• Kolme või enama täisarvu suurim ühine jagaja ja väikseim ühine korrutis

Pange tähele, et standardraamatukogus olevate funktsioonide spetsifikatsioonid erinevad sõltuvalt Pythoni versioonist. Selles artiklis on näidatud ka standardraamatukogus mitteoleva funktsiooni rakendamise näide.

• Python 3.4 või varasem
  • GCD:fractions.gcd()(ainult kaks argumenti)
• Python 3.5 või uuem
  • GCD:math.gcd()(ainult kaks argumenti)
• Python 3.9 või uuem
  • GCD:math.gcd()(toetab rohkem kui kolme argumenti)
  • väikseim ühine nimetaja:math.lcm()(toetab rohkem kui kolme argumenti)

Siinkohal selgitame meetodit, kasutades Pythoni standardset raamatukogu; NumPy abil saab hõlpsasti arvutada suurima ühise jagaja ja väikseima ühise kordaja mitme massiivi iga elemendi jaoks.

Kahe täisarvu suurim ühine jagaja ja väikseim ühine korrutis

GCD

Alates Python 3.5 on matemaatikamoodulis olemas funktsioon gcd(). gcd() on akronüüm, mis tähendab

• greatest common divisor

• math.gcd() — Mathematical functions — Python 3.10.2 Documentation

Tagastab argumendis määratud täisarvu suurima ühise jagaja.

import math

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

Pange tähele, et Python 3.4 ja varasemates versioonides on funktsioon gcd() fraktsioonide moodulis, mitte matemaatika moodulis. fractions tuleb importida ja fractions.gcd().

• fractions.gcd() — Rational numbers — Python 3.10.2 Documentation

väikseim ühine nimetaja

Python 3.9 lisati matemaatikamoodulisse funktsioon lcm(), mis tagastab väikseima ühise korrutise. lcm on akronüüm sõnadest

• least common multiple

• math.lcm() — Mathematical functions — Python 3.10.2 Documentation

Tagastab argumendis määratud täisarvu väikseima ühise kordaja.

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

Enne Python 3.8 ei pakuta funktsiooni lcm(), kuid seda saab hõlpsasti arvutada, kasutades funktsiooni gcd().

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

Rakendamise näide.

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

print(my_lcm(6, 4))
# 12

/Kuna selle tulemuseks on kümnendkordse ujukoma, kasutatakse kahte kaldkriipsu kümnendkriipsu kärpimiseks ja täisarvulise jagamise tulemuse tagastamiseks. Pange tähele, et ei toimu mingit töötlemist, et teha kindlaks, kas argument on täisarv või mitte.

Kolme või enama täisarvu suurim ühine jagaja ja väikseim ühine korrutis

Python 3.9 või uuem

Alates Python 3.9 toetavad kõik järgmised funktsioonid rohkem kui kolme argumenti.

• 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

*Kui soovite arvutada loendi elementide suurima ühise jagaja või väikseima ühise kordaja, täpsustage argument sellega.

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

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

Python 3.8 või varasem

Enne Python 3.8 toetas funktsioon gcd() ainult kahte argumenti.

Kolme või enama täisarvu suurima ühise jagaja või väikseima ühise korrutise leidmiseks ei ole vaja mingit eriti keerulist algoritmi; arvutage lihtsalt suurima ühise jagaja või väikseima ühise korrutise väärtus iga korrutise jaoks kordamööda välja, kasutades kõrgema astme funktsiooni reduce().

• functools — Higher-order functions and operations on callable objects — Python 3.10.2 Documentation

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

Pange taas tähele, et enne Python 3.4 on funktsioon gcd() fraktsioonide moodulis, mitte matemaatikamoodulis.

väikseim ühine nimetaja

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