I'm a student in the 10th grade and our teacher assigned some exercises. I'm pretty advanced in my class but one exercise is just isn't coming together as I want. The exercise is as follows:

Given the numbers between 100,000 and 200,000, find the number with the most divisors (as in which number can be divided with the most numbers, any number).

I wrote something but it executes in 32 seconds(!) and I just can't figure out the logic behind it (I can't even check if the answer is correct).

This is the code that I wrote:

void f3() {
    int mostcount = 0, most, divisors = 0;
    for (int i = 100000; i <= 200000; i  ) {
        for (int j = 1; j<=i/2; j  ) {
            if (i % j == 0) {
                divisors  ;
            }
        }
        if (divisors > mostcount) {
            mostcount = divisors;
            most = i;
        }
        divisors = 0;
    }
    cout << most << endl;
    return;
}

The output:

166320

Edit: My question is how can I reduce the runtime?

I'd be really thankful if you could explain your answer if you do decide to help, instead of just saying that I could do this with an XYZ type binary tree.

CodePudding user response：

Using @AhmedAEK 's response: "replace j<=i/2 with j<=sqrt(i), you only need to loop up to that, also #include <math.h> at the top, you also need to multiply the total divisors by 2, since there is a number above the sqrt that reflects the number below the sqrt. ie: 1000 is 10 x 100."

void f3() {
    int mostcount = 0, most, divisors = 0;
    for (int i = 100000; i <= 200000; i  ) {
        for (int j = 1; j<=sqrt(i); j  ) {
            if (i % j == 0) {
                divisors  ;
            }
        }
        if (divisors > mostcount) {
            mostcount = divisors;
            most = i;
        }
        divisors = 0;
    }
    cout << most << endl;
    return;
}

Thanks!

CodePudding user response：

Since you tagged this with performance...

You can find all the prime factors of your input value (and the number of times they occur), and calculate the number of ALL divisors by multiplying those counts 1. This example cut the time by almost 5 times!

void f() {
    int mostcount = 0, most = 0;
    for (int i = 100000; i <= 200000; i  ) {
        int divisors = 1;
        int x = i;
        int limit = sqrt(i);

        int count = 0;
        for (int j = 2; j <= limit; j  ) {
            int count = 0;
            while (x % j == 0) {
                count  ;
                x /= j;
                limit = sqrt(x);
            }
            divisors *= count   1;
            if (j > 2)
                  j;
        }
        if (x > 1)
            divisors *= 2;
        if (divisors > mostcount) {
            mostcount = divisors;
            most = i;
        }
    }
    cout << most << ", " << mostcount << endl;
    return;
}

If you find a list of prime numbers, you can cut that time in half:

static vector<int> primes = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 
    83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 
    197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 
    331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449 };

void f() {
    int mostcount = 0, most;
    for (int i = 100000; i <= 200000; i  ) {
        int divisors = 1;
        int x = i;
        int limit = sqrt(i);

        for (int j: primes) {
            if (j > limit) break;
            int count = 0;
            while (x % j == 0) {
                count  ;
                x /= j;
            }
            limit = sqrt(x);
            divisors *= count   1;
        }
        if(x > 1) 
            divisors *= 2;
        if (divisors > mostcount) {
            mostcount = divisors;
            most = i;
        }
    }
    cout << most << ", " << mostcount << endl;
    return;
}

Explanation: let's take 166320. It's prime factors are:

• 2 (4 times)
• 3 (3 times)
• 5 (once)
• 7 (once)
• 11 (once)

Here, 2 produces 5 combination (it may go into the divisor 0 to 4 times), 3 - 3 combinations, and so on.

So you get 5 * 4 * 2 * 2 * 2 = 160 divisors. Strictly speaking, you should add one more - the input number itself.