Hogyan lehet két számnak a legkisebb közös többszörösét megtalálni?

Az adott számokat felbontod prímszámok szorzatára, majd összeválogatod őket a következő módon:

Pl. 14,15 és 18 legkisebb közös többszöröse:

14 = 2*7

15 = 3*5

18 = 2*3*3

A közös többszörösnek szorzatára bontva tartalmaznia kell a következő prímszámokat: 2,3,5,7 a következő mennyiségekben:

2 - csak egyszer szerepel a 14-ben és a 18-ban, tehát ebből egy darab kell.

3 - a 15-ben egyszer szerepel, viszont a 18-ban kétszer, tehát ebből kettő darab kell.

5 - a 15-ben csak egyszer szerepel, tehát ebből egy darab kell

7 - a 14-ben csak egyszer szerepel, tehát ebből csak egy kell.

Ahhoz hogy mindhárom számmal tudjuk osztani a legkisebb közös többszöröst, a fent leírt prímszámoknak az adott mennyiségben kell szerepelniük a legkisebb közös többszörös szorzatra bontott alakjában. Tehát:

A 14,15,18 legkisebb közös többszöröse szorzatra bontva:

2*3*3*5*7 ami kiszorozva 630.

felhasználva hogy

> a*b = [a,b]*(a,b)

(a,b), vagyis a legnagyobb közös osztó, pedig viszonylag könnyen számolható az euklideszi algoritmussal

(például ha minimálisan programozható számológéped van, de interneted nincs)