Ilość dzielników liczby

 Algorytmy zapisalem w pseudokodzie
{     - Pascalowe BEGIN
}     -    -"-    END
%     - reszta z dzielenia, w Pascalu MOD
floor - czesc calkowita liczby, w Pascalu TRUNC
\     - dzielenie całkowitoliczbowe, w C poprostu /, w Pascalu DIV
x++   - czyli x=x+1, w Pascalu INC(x)
z*=v  - z=z*v
z+=v  - z=z+v

naiwny(n){
  result= 1                      //  1
  for (i= 2 ... n)
    if (n % i == 0)
      result += 1
}

pierwiastek(n){
  if (n < 2) result= 1
  else {
    p= floor(sqrt(n))            //  2
    if (p*p == n) {              //  3
      p-=1
      result=3
    } else result=2              //  4
    for (i= 2 ... p)
      if (n % i == 0)
        result += 2              //  5
  }
}

pierwsze(n) {
  result= 1
  d= 2
  while (d*d <= n) {             //  6
    s= 1
    while (n % d == 0) {
      n= n \ d
      s++                        //  7
    }
    result *= s                  //  8
    d++
  }
  if (n > 1) result *= 2         //  9
}

pierwsze2(n) {
  result= 1
  d= 2
  k= 2;
  while (d*d <= n) {
    s= 1
    while (n % d == 0) {
      n= n \ d
      s += 1
    }
    result *= s
    if (d>2) then d += 2         // 10
    else d= 3
  }
  if (n>1) then result *= 2
}

pierwsze23(n) {
  result= 1
  d= 2
  k= 2
  while (d*d <= n) {
    s=1
    while (n % d == 0) {
      n= n \ d
      s += 1
    }
    result *= s
    if (d == 2) d=3
    else if (d == 3) d=5
    else {                       // 11
      d+=k
      k= 6-k                     // 12
    }
  }
  if (n > 1) then result *= 2
}

1- każda liczba dzieli się przez jeden

2- w poprzednim algorytmie sprawdzaliśmy czy liczby z zakresu od 2 do n są dzielnikami liczby n. Sprawdzany zakres można istotnie zmniejszyć.

3 - jeżeli liczba (>=2) jest kwadratem, wtedy ma przynajmniej 3 dzielniki: 1, pierwiastek(n), n.

4 - jeżeli nie jest to przynajmniej dwa, tzn. 1 oraz n.

5 - jeżeli i jest dzielnikiem n to także n/i jest dzielnikiem n

Jeżeli interesuje nas tylko liczba dzielników n możemy skorzystać z rozkładu liczby na czynniki pierwsze. Każda liczba większa od jeden jest albo liczbą pierwszą, albo da się ją przedstawić jako iloczyn liczb pierwszych. Pewne liczby pierwsze mogą pojawić się wielokrotnie, np. 20 = 2 * 2 * 5 = 2^{2 * 3}0 * 5^{1 * 7}0 * 11^0...
Liczba dzielników danej liczby to iloczyn powiększonej o jeden potęgi w jakiej występują liczby pierwsze w rozkładzie. W tym przykładzie liczba dzielników to (2+1)(0+1)(1+1)(0+1)(0+1)*...

6 - oczywiście nie warto sprawdzać podzielności n przez liczby większe od jej pierwiastka.

7 - zliczamy ile razy n dzieli się przez d

8 - kolejny czynnik liczby dzielników

9 - jeżeli pozostał jeszcze czynnik pierwszy wtedy liczba dzielników wzrasta dwukrotnie

10 - skoro sprawdziliśmy podzielność przez 2, to możemy pominąć testowanie podzielności przez pozostałe liczby parzyste

11 - łatwo pominąć nie tylko liczby parzyste ale także wielokrotności liczby 3.
Sprawdzać można tylko podzielność przez 2, 3, 5, 7, 11, 13, 17, 19, 23, 25,...

12 - k (skok o jaki zmienia się d) przyjmuje na przemian wartości 2 i 4.

W celu sprawdzenia szybkości działania, liczyłem sumę liczby dzielników liczb od jeden do liczby podanej w tabelce. Czas w sekundach.

  algorytm   |100000|229373|4000000|11500000|18500000|24000000
-------------+------+------+-------+--------+--------+--------
naiwny       |224   |      |       |        |        |
pierwiastek  |  0,9 | 3    | 224   |        |        |
pierwsze     |  0,3 | 0,9  |  49   |   224  |        |
pierwsze2    |  0,22| 0,37 |  25,6 |   112  |   224  |
pierwsze23   |  0,17| 0,56 |  17,7 |    77  |   152  |  224
-------------+------+------+-------+--------+--------+--------

Jak widać w dość prosty sposób uzyskano 1300 krotne przyśpieszenie, albo inaczej, w tym samym czasie sprawdzono 240 razy większy zakres.

Dysponując rozkładem na czynniki pierwsze, łatwo otrzymać także wszystkie dzielniki danej liczby.
I jest to sposób szybszy niż polegający na algorytmie NAIWNYm czy PIERWIASTku.
Liczby 64 bitowe nie mają więcej niż 16 różnych czynników pierwszych. Ale to inna historia.
-------------------------------------------------------------------------------------------------------------------[ Xitami ]---