Lexiq

Prímtényezős felbontás

A prímtényezős felbontás (vagy más néven prímfelbontás, prímfaktorizáció vagy törzstényezős felbontás), egy szám prímszámok szorzataként való felírását jelenti. Minden 1‑nél nagyobb pozitív egész szám csak egyféleképpen bontható fel ilyen módon.

A 12 prímtényezős felbontása például 2*2*3, a 39‑nek pedig 3*13.

Egy szám prímtényezős felbontását az alábbi módon lehet megkapni:

  1. Ha a szám prím, akkor írd fel a prímtényezős felbontás listájába, és készen vagy.
  2. Ha a szám nem prím, keresd meg a legkisebb prímet, amivel maradék nélkül osztható (ehhez egymás után meg kell próbálni elosztani az egyes prímszámokkal).
  3. A 2. pontban kapott prím lesz a prímtényezős felbontás egyik eleme, írd fel a listába, majd oszd el vele a számot!
  4. Ugorj az első pontra, és ismételd meg az eljárást a 3. pontban végzett osztás eredményét használva.

Ha például a 45 prímtényezős felbontása érdekel, akkor

Az eredmény tehát 3*3*5.