: index | programowanie | webmastering | algorytmika | download | projekty | słownik | grafika | flash | linki :

a l g o r y t m y > działania na liczbach >

I L O Ś Ć   D Z I E L N I K Ó W   L I C Z B Y   N A T U R A L N E J

 

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 29 30

 
       

Liczbą pierwszą nazywamy liczbę naturalną nie mniejszą niż 2 posiadającą dokładnie dwa dzielniki naturalne. Najprostszą metodą wyznaczenia ilości wszystkich dzielników liczby N jest sprawdzenie podzielności liczby N przez wszystkie możliwe wartości, tj, 1, 2, ..., N, lub podzielności przez 2, 3, ..., N-1 i dodatnie do otrzymanego wyniku liczby 2:

Function IleD(N : LongInt) : Byte;
Var
  I, Wynik : Byte;
Begin
  If N<=0 Then IleD:=0
  Else
    If N=1 Then IleD:=1
    Else
      Begin
        Wynik:=2;
        For I:=2 To N-1 Do
          If (N Mod I)=0 Then Inc(Wynik); {Wynik:=Wynik+1}
        IleD:=Wynik;
      End;
End;

Znacznie lepszy algorytm wyznaczania ilości dzielników liczby naturalnej oparty jest o elemetarne twierdzenie teorii liczb dotyczące podzielności liczb.

Twierdzenie: Jeżeli c jest liczbą pierwszą, c|a*b i liczby c i a są względnie pierwsze (tzn. NWD(c, a)=1), to c|b.

Z twierdzenia tego można łatwo wyciągnąć interesujący wniosek: jeżeli a*b=c*d oraz wszystkie liczby są pierwsze, to a=c lub a=d. Ponieważ a|a*c, to jeśli a<>c, to NWD(a, c)=1 (są to liczby pierwsze), więc a|d. Ponieważ a i d również są liczbami pierwszymi, więc podzielność ta jest możliwa tylko wówczas gdy a=d.
Wniosek: Iloczynu dwóch liczb pierwszych nie można zastąpić iloczynem innych dwóch liczb pierwszych.
Rozumując podobnie można dojść do wniosku, że dowolny iloczyn liczb pierwszych jest niepowtarzalny, tzn. nie da się go otrzymać z iloczynu innej kombinacji liczb pierwszych. Ta obserwacja pozwala na dużo szybsze wyznaczenie ilości dzielników liczby naturalnej.
Niech p=p1*p2*...*pn, gdzie pi są różnymi liczbami pierwszymi, np. 2*3*7*11*29. Liczba p jest podzielna przez 1 i p oraz przez każdy z czynników iloczynu, co daje n+2 dzielniki. Liczba p dzieli się również przez iloczyn każdej pary czynników - par takich jest (n po 2)=n*(n-1)/2. Podobnie liczba p jest podzielna przez iloczyn każdej trójki, czwórki, itd. aż do iloczynu n-1 czynników.
Łącznie daje to n+2+(n po 2)+(n po 3)+...+(n po (n-1)) dzielników. Ponieważ n=(n po 1), zaś 2=1+1=(n po 0)+(n po n), więc ostatecznie liczba p posiada (n po 0)+(n po 1)+...+(n po n) dzielników. Na podstawie wzoru na potęgę dwumianu (tzw. wzór Newtona) powyższa suma wynosi 2n (należy zastosować ten wzór do dwumianu (1+1)n).

Tak więc, jeśli w rozkładzie liczby na n czynników pierwszych każdy dzielnik występuje tylko raz (posiada stopień 1), to liczba ma 2n dzielników.

Trochę gorzej wygląda to gdy dzielniki rozkładu się powtarzają. Rozważymy taką sytuację na przykładzie: 60=2*2*3*5. Liczba 60 posiada dzielniki: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60, czyli łącznie 12. Po usunięciu jednego powtarzającego się dzielnika otrzymamy liczbę 30=2*3*5 i posiadającą 23 dzielników. Dodając do zbioru dzielników liczbę 2 pojawią się nowe dzielniki 4, 12, 20, 60. Jak łatwo zauważyć są to iloczyny liczby 4 przez możliwe do otrzymania dzielniki z cyfr pozostałych, tj. 3 i 5.
Gdyby rozważyć liczbę 120=2*2*2*3*5, to okazałoby się, że pojawiły się dodatkowo ponownie cztery dzielniki 8, 24, 40 i 120, będące ponownie iloczynem liczby 8 przez możliwe do uzyskania dzielniki z liczb 3 i 5. Pozwala to wyciągnąć wniosek, że liczba postaci p=p1k*p2*...*pn posiada (k+1)*2n-1 dzielników.

Można udowodnić, że liczba postaci p=p1k1*p2k2*...*pnkn posiada

(1+k1)*(1+k2)*...*(1+kn)*2N-R dzielników

gdzie N jest ilością różnych dzielników, R ilością dzielników o stopniu co najmniej 2, zaś iloczyn przed potęgą liczby 2 zawiera tylko te czynniki postaci (1+ki), w których ki>1.

Dla przykładu: liczba 360=2*2*2*3*3*5 posiada (1+3)*(1+2)*23-2=24 dzielniki: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360.