Thread: Dividers

Step 1 is learn how to indent code. It helps everyone (including you) to figure out what is going on.

Code:

#include <stdio.h>
#include <math.h>

int main()
{
    int n, i, br, max, p, k;

    scanf("%d", &n);
    max = 0;

    for (i = 1; i <= n; i++) {
        br = 0;
        for (k = 1; k <= sqrt(i); k++) {
            if (i % k == 0)
                br++;
            if (br > max) {
                max = br;
                p = i;
            }
        }
    }

    printf("%d\n%d\n", p, br);

    return 0;
}

SourceForge.net: Indentation - cpwiki

> int n, i, br, max, p, k;
Next, give all your variables some meaningful names, not cryptic 1 or 2 letters.

For example,
int currentBestNumber, currentBestNumDivisors;

Step 3 is to describe what your program is doing wrong.

Originally Posted by Dule

program is doing fine, but its not absolutely correct

Well, if it was doing fine, then it would be correct, wouldn't it? You need to identify what is not correct about what you have.

(Upon a second reading, please tell me the answer isn't "I was printing br when I was supposed to be printing max.")

Originally Posted by Dule

program needs to be faster...

Upgrade some hardware, then. [If you actually want fancy, then you need to do some prime factorization (not just any old factorization) and use the (n1+1)(n2+1)(n3+1)...(nk+1) formula, where the n's are the exponents on the prime factors.] EDIT: Actually there is one really easy change you can make that will probably speed things up a lot, and that's moving the calculation of the square root outside of your loop, since it doesn't change. You can also move the checking against max outside of the inner loop as well.

Originally Posted by Dule

and there is no part in code that ask what if there are two with same numbers of dividers

According to the specifications you posted, any attempt to do so would be incorrect, so I am curious as to why you would want such a thing.

Mmmm, faster you say - how about turning on the optimiser?

Code:

$ gcc baz.c -lm
$ time ./a.out 
1000000
720720
25

real	0m35.909s
user	0m31.498s
sys	0m0.036s

# Optimise it
$ gcc -O2 baz.c -lm
$ time ./a.out 
1000000
720720
25

real	0m21.969s
user	0m19.625s
sys	0m0.020s

# Now with tabstop's suggestions
$ gcc -O2 baz.c -lm
$ time ./a.out 
1000000
720720
25

real	0m17.691s
user	0m15.297s
sys	0m0.028s
$

Twice as fast is very achievable with some simple changes.

But if you want it to be really fast, you need a better algorithm (assuming one exists).

I would at least move the square root out of the loop, but better yet, you can eliminate it entirely by keeping it in a variable say 'rootN' and only increment it when rootN*rootN is less than N.