## Thursday, 4 August 2011

### Finding the count of factors of a number

Question

This is more of a mathematical and a GMAT/CAT question rather than a programming one. But found this question very interesting and found it from Project Euler.

Before seeing the solution, please try out yourselves.

Let me reiterate the question,

“Find a number which has more than 500 factors. The number is part of a triangle series or natural series of additions”

Triangular number is given a name since it can fill every point in a triangle and will add up like this,

1+2+3+4…+n = n(n+1)/2

The above is sometimes called arithmetic series sum as well.

If you need some mathematical background about finding factors, see the below video,

I really loved the second brute force method given in the above video since its simple and easier to visualize and program.

I got into lots of problem since I didn’t make up the triangular number in my mind after I got that clear, zoom I got the answer. Number of trails would be at least 20 times. :)

First tried manually using calculators. But it didn’t work out since I didn’t see that I need to calculate only for triangular number.

Do the second method of factorizing start from 1 and go up by triangular series and count the number of factors.

The Method is,

1.  find sqrt(number)

2. If the sqrt is a perfect square, then set diff to –1

3. run a loop from 1 to sqrt(number) and count how many numbers are dividing the triangular number selected

4. count*2+diff gives the total factors.

Code

` `
`#include <math.h>`
` `
`void main(int argc, char* argv[])`
`{`
`    int data=0; //pow(35.00,13.00);`
`    int next=1;`
`    int max = 0;`
` `
`    while(1) {`
`    int count=0;`
`    int diff = 0;`
`    data = data+next;`
`    int mid = (int) floor(sqrt((double)data));`
`    if(mid * mid == data) `
`        diff = -1;`
`    `
`    for(int j=1;j<=mid;j++) {`
`        if(data % j == 0) {`
`            ++count;`
`        }`
`    }`
`    count = count*2+diff;`
`    if(count > max) {`
`        max = count;`
`        cout<<data<<"="<<count<<endl;`
`        if(max > 499) `
`            break;`
`    }`
`    next++;`
`    }`
`}`