Ebben a kiadványban megvizsgáljuk, mik azok a prímtényezők, és hogyan bonthatunk fel tetszőleges számot ezekre. Az elméleti anyagot példákkal kísérjük a jobb megértés érdekében.
Tartalom
Algoritmus egy szám prímtényezőkre bontására
Kezdésként emlékezzünk rá egyszerű egy nullánál nagyobb természetes szám, amely csak önmagával és eggyel osztható (az „1” nem prím).
Ha kettőnél több osztó van, akkor a számot veszi figyelembe összetett, és felbontható prímtényezők szorzatára. Ezt a folyamatot ún faktorizáció, a következő lépésekből áll:
- Gondoskodunk arról, hogy a megadott szám ne prím legyen. Ha 1000-ig, akkor ebben a külön bemutatott táblázat segíthet.
- Az osztó megtalálása érdekében rendezzük az összes prímszámot (a legkisebbtől).
- Elvégezzük az osztást, és a kapott hányadosra a fenti lépést. Ha szükséges, ismételjük meg ezt a műveletet többször, amíg prímszámot nem kapunk.
Faktorizációs példák
Példa 1
Bontsuk fel a 63-at prímtényezőkre.
Döntés:
- A megadott szám összetett, így lehet faktorozni.
- A legkisebb prímosztó három. A 63 hányadosa 3-mal 21.
- A 21-es szám is osztható 3-mal, így 7-et kapunk.
- A hét egy prímszám, ezért megállunk ennél.
A faktorizáció általában így néz ki:
Válasz: 63 = 3 3 7.
Példa 2
Példa 3