Nagy számok prímszámokra való bontását hogy kell elvégezni? Legnagyobb közös osztó, legkisebb közös többszörös?

Legnagyobb közös osztóra ismerek egy módszert: euklideszi algoritmus.

Az a lényeg, hogy van két számod, pl. 10835 és 54321. Fogod a nagyobb számot, felbontod úgy, hogy felírod, mennyiszer van meg benne a kisebb szám, és hozzá adod a maradékot.

Tehát: 54321=5*10835+146.

Innentől ugyanez a módszer, csak most az 10835-t kell osztani 146-tal, felírod, hányszor van meg benne, és hozzáadod a maradékot, és így viszed tovább addig, míg nem lesz 0 a maradék. A 0-t megelőző maradék lesz a legnagyobb közös osztó.

Hogy érhető legyen:

10835=74*146+31

146=4*31+22

31=1*22+9

22=2*9+4

9=2*4+1

4=4*1+0

Itt az 1 lesz a legnagyobb közös osztó, mert az a 0 előtti maradék.

(10385;54321)=1

Legkisebb közös többszörös:

"A legnagyobb közös osztó felhasználásával

Nagy számok esetén a törzstényezős felbontás nehéz feladat, de a legkisebb közös többszörös és a legnagyobb közös osztó kapcsolata ekkor is hatékony módszert ad.

Ugyanis két szám szorzata egyenlő legnagyobb közös osztójuk, és legkisebb közös többszörösük szorzatával. Ez hatékony módszert ad a legkisebb közös többszörös meghatározására, mivel elég az euklideszi algoritmussal meghatározni a legnagyobb közös osztót, összeszorozni a két számot, majd a szorzatot elosztani a legnagyobb közös osztóval." (Wikipédia)

Annyit kiegészítésként, hogy az Euklideszi algoritmus nem a prímszámok használatára épül, mint láthatod. De remélem tudtam segíteni a LNKO és LKKT kérdésében.

(Természetesen az osztásokat célszerű számológéppel elvégezni. Ez is tud lenni hoszabb folyamat, ha nagyon nagy a számod, de jóval rövidebb, mint prímtényezőkre való bontogatás.)

Az euklideszi algoritmusnak pont az a lényege, hogy az egyik nincs meg egésszer a másikban. Fogod az egyik számot, elosztod _maradékosan_ a másikkal, majd az osztó lesz az osztandó, a maradék meg az osztó. Az idézett wiki cikkben van két szép példaprogram is.

Pl.:

(698120:68857)

698120:68857 maradéka 9550

68857:9550 maradéka 2007

9550:2007 maradéka 1522

2007:1522 maradéka 485

1522:485 maradéka 67

485:67 maradéka 16

67:16 maradéka 3

16:3 maradéka 1

3:1 maradéka 0, itt a vége az eljárásnak. Az utolsó osztó az 1, ez lesz a közös osztó. A két szám relatív prím, legkisebb közös osztó a két szám szorzata.

Ja, ha prímekre akarsz bontogatni, akkor meg javaslom az alábbi tételt: Bármely szám legkisebb valódi osztója prím. Azaz elkezdjük osztani kettővel, amíg lehet. Ha nem lehet, akkor az osztót eggyel növeljük, és újra próbálkozunk, ezt csináljuk egészen addig, amíg az osztó nagyobb nem lesz az osztandónál. Például az 542612 prímosztói:

542612:2=271306, az osztók: {2}

271306:2=135653, {2,2}

135653:2 nem osztható, a következő a 2+1=3

135653:3 szintén nem osztható, 3+1=4

135653:4 nem osztható, 4+1=5

135653:5 n.o., 5+1=6

135653:6 n.o., 6+1=7

135653:7=19379, {2,2,7}

19379:7 n.o., 7+1=8

19379:8 n.o., 8+1=9

19379:9 n.o., 9+1=10

19379:10 n.o., 10+1=11

stb... Ez egyébként prímszám, úgyhogy 542612=2^2*7*19379. Pont a nagy hézagok miatt ezt kézzel nem, de géppel szokták számoltatni. Ha iskolában kézzel kell, és 100 alatt már nincsen prímtényező, akkor a lehetőségek:

A) a tanár számolta el;

B) te számoltad el.

Jellemzően a B szokott megtörténni, de már velem is előfordult, hogy két számjegy felcserélésével megtörtént az A eset.