Jelenlegi hely

Prím tényezőkre bontás

Egy adott szám azon osztóit amelyek prím számok, prím osztóknak hívjuk. A  számot felírhatrjuk prímosztók szorzataként, és az így használt prímosztók  a szám prímtényezői.

Pl: 12 prímtényezői: 2,2,3
      A 12 osztói az 1, 2, 3, 4, 6, 12. Ezekből prímszám: 2, 3. A 12 felírható:
      12=2*2*3 formában.

Az algoritmus:

List<int> tenyezok= new List<int>();

int i=2;
            
while(i<=szam)
{
            
       if (szam%i==0)
      {
                    tenyezok.Add(i);
                    szam=szam/i;
      } else i=i+1;
                
}

Mit csinál az algoritmus:
Mivel az 1 nem prím szám, így nem is azzal kezdi az osztást. A 2 már az. Addig osztja ezzel az i-vel a számot amíg maradék nélkül meg tudja tenni. Minden sikeres osztásnál a i-t a prím tényezők listájához hozzáadja (2048 esetében 11x) és a szám i-ed részével dolgozik tovább. Ha már az aktuális i-vel nem tudja maradék nélkül osztani, akkor i+1-el próbálja addig amíg maradék nélkül megteheti, ahogy az előbbi i-nél is.

A fenti algoritmus hátránya:

  • a 2 többszöröseivel fölöslegesen próbálkozik osztani
  • elég lenne a számunk négyzetgyökéig dolgozni

 

 

 

Theme by Danetsoft and Danang Probo Sayekti inspired by Maksimer