Najszybsze obliczanie ilości dzielników liczby

Question

Witam. Mam za zadanie obliczyć ilość dzielników danej liczby. Na wejściu są liczby od 0 do 1000000000.

Taki kodzik nie działa we wszystkich przypadkach (za długi czas pracy przy większych liczbach). 

#include <iostream>

using namespace std;
long long a,b=1;
int main()
{
    cin>>a;
    for(int i=1;i<a;i++)
    {
        if(a%i==0) b++;
    }
    cout<<b;
    return 0;
}

Zna ktoś szybszy sposób?

Answer 1

http://www.matematyczny-swiat.pl/2013/02/dzielniki-naturalne-liczby-naturalnej.html

Idea ogólnie jest taka: rozbijasz liczbę na iloczyn liczb pierwszych (prime factorization), bierzesz potęgi poszczególnych liczb i podstawiasz do wzoru (a1 + 1) * (a2 + 1)...

40 = 2^3 * 5^1 -> (3 + 1) * (1 + 1) = 4 * 2 = 8 -> 40 ma 8 dzielników

Sam zaimplementowałem taki algorytm i jest on o wiele szybszy niż ten tutaj przedstawiony.

Comments

Dzięki wielkie pomogło