Nejmenší společný násobek

O(a·b / gcd(a,b))

Nejmenší společný násobek (NSN) dvou celých čísel a a b je nejmenší kladné celé číslo, které je dělitelné oběma. Přímý postup: vyjmenujeme násobky většího čísla (m, 2m, 3m, …) a zastavíme se u prvního, který je dělitelný i menším číslem. To trvá nejvýše menší/gcd(a,b) kroků, protože lcm(a,b) = větší · (menší / gcd(a,b)). NSN se uplatňuje při sčítání zlomků, plánování opakujících se událostí a hledání period v modulární aritmetice.

Posloupnost
Stiskni ▶ a spusť
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Zvolíme větší hodnotu m a menší hodnotu s
  2. Vyjmenujeme násobky k·m pro k = 1, 2, 3, …
  3. Zkontrolujeme, zda je každý násobek dělitelný hodnotou s
  4. První násobek, který projde testem, je nsn(a, b)

Pseudokód

1lcm(a, b):                           # O(b / gcd(a,b)) where b = larger2  m = max(a, b);  s = min(a, b)3  for k = 1, 2, 3, ...:4    if (k * m) % s == 0:5      return k * m              # found lcm