[RESOLVED] Calculating Number of Divisors

[BlindSniper]

Hi all,
I'm currently working on project euler problem 12 and my code is working, only problem is that it is to slow.

int  getDivisors(int n)
{
    int c = 0; // the counter
    for (int i = 1; i < n; i++)
    {
        if (n % i == 0)
            c++;
    }
    return c;
}

Quick explanation, It is a loop that goes from 1 to the value you gave the function and if the value divided by the Iterator is 0 it increments the counter.
this works but gets extremely slow when large digits are involved (I did a profiling test and 99.9% of my programs running time is spent in this function)

Is there a way to calculate the number of divisors of a number instead of my brute force attempt ?

[jemidiah]

I would do the problem completely differently by appealing to prime factorizations. The answer appears to be n=12375, so the brute force method you're using would stall out well before then (the n=12000 case requires around 144 million runs through your loop).

You can make your brute force method much more efficient by checking for divisors only up to the square root of the number. Divisors typically come in pairs, eg. 2*6 = 12, though once in a while do not, eg. 3*3 = 9.

(I've been purposefully vague. Please ask for clarification if needed.)

[BlindSniper]

my method actually worked after a few minutes, but now I've rewritten it and it is much Faster.

int  getDivisors(int n)
{
    int c = 0;
    for (int i = 1; i < ceil(sqrt(n)); i++)
    {
        if (n % i == 0) 
            c+=2; // mirror factor
        
    }
    return c;
}

Takes about 2 seconds to do the task now

[jemidiah]

I'm curious, how long did it take to run the first time? My machine took about 45 seconds to run the n=12000 to 12100 range with the inefficient method.

[BlindSniper]

I don't really know C++ very well and I don't know how to time in C++, I could time it with my phone's stopwatch but it would be about +-500 ms wrong

[BlindSniper]

Ok, With my first method on my computer core I5 2500 @ 3.3 ghz in C++ compiled 64 bit with the range n 12300 to 12400 it took 23.8 seconds.