1

I have a problem on coderforces that called divisors.

I believe that I had solved it, but it gives me a time limit exceeded error so I had tried my best to make it shorter but still the same error.

In the problem I have to give how many divisors the number should have.

My code is:

#include <iostream>
using namespace std;
int main(){
    long long  t, x;
    int res = 2;
    cin >> t;

    for (int j = 0; j < t; j++){
        cin >> x;
        for (int i = 2; i <= x / 2; i++){
            if (x%i == 0){
                res++;
            }
        }
        cout << res << endl;
    }
    return 0;
}

Example input should be:

3

12

7

36

The output should be:

6

2

9

Community
  • 1
  • 1
Mostafa Ibrahem
  • 31
  • 1
  • 6

3 Answers3

0

You could "split" your inside loop (the one that counts the divisors of the current number) in two separate case, based on whether the current number is odd or even: if it is odd, then you only have to check the division with odd numbers, starting from 3.

Anyway, you can optimeze the inner loop a bit more by checking only the numbers from 2 to floor(sqrt(x)). If a number x is divisible by i, then it will also be divisible by x / i, so instead checking the numbers from 2 to x / 2, look only until (int) sqrt(x) (it is not absolutely necessary to cast the result of sqrt, since i is int).

The code for the inner loop might look like this:

for (int i = 2; i <= (int)sqrt(x); i++) {
    if (x % i == 0)
        res += 2;
}
Polb
  • 640
  • 2
  • 8
  • 21
  • i think i understand what you are saying but how do i look until **(int) sqrt(x/2)** i didn't understand this one – Mostafa Ibrahem Jul 23 '16 at 19:13
  • I added a code snippet to make things a bit clearer. – Polb Jul 23 '16 at 19:17
  • @MostafaIbrahem My bad, I typed something wrong, the loop goes until `sqrt(x)`, not `sqrt(x / 2)` (corrected that). – Polb Jul 23 '16 at 19:19
  • i didn't understand what you meant by counting until `(int) sqrt(x/2)` and how to use it sorry i'm beginner – Mostafa Ibrahem Jul 23 '16 at 19:21
  • i made the loop until it goes to `sqrt(x)` but it output **4** instead of **6** when i enter **12** – Mostafa Ibrahem Jul 23 '16 at 19:23
  • It means iterating through all the numbers from 2 to `(int)sqrt(x)` (in our examples) and translated into code it looks like the `for` loop in the answer. – Polb Jul 23 '16 at 19:23
  • Let's see... initially `res` is 2. We start iterating from 2. `(int)sqrt(12)` is 3. So our `i` will only go through 2 and 3. For 2: `12 % 2 == 0` so now `res` is incremented by 2. Now `res` is 4. Next, `i` is 3. `12 % 3 == 0` so now `res` is now incremented by 2 again, `res == 6`. Are you sure you reset `res` to 2 for each number? – Polb Jul 23 '16 at 19:25
  • the number 12 and most numbers worked but when i enter **36** it prints **10** can you please tell me why? it should be 9 i think – Mostafa Ibrahem Jul 23 '16 at 19:47
  • This happens because sqrt(36) is a perfect square, so the algorithm is counting 6 two times, one from `i = 6` and the other from `i = 36 / 6`, which yields exactly 6. You can add an extra check for perfect squares, like `if (sqrt(x) == (int)sqrt(x) && i == sqrt(x)) res++; else res += 2;` – Polb Jul 23 '16 at 19:55
0

First your code:

#include<iostream>
using namespace std; // poluting namespace
int main(){
long long  t, x; // <------- EVIL use int64_t if that is what you want.
int res = 2; // is never reset is that your intent?
             // what if x == 1???
cin >> t;

for (int j = 0; j < t; j++){ // comparing an int32_t with an int64_t ...
    cin >> x; // stream has seldom been accused of being fast but is not likely to be the problem.

    for (int i = 2; i <= x / 2; i++){ // as already suggested stop at sqrt(x) or see below.
        if (x%i == 0){ // % is a costly operation.
            res++;
        }
    }
    cout << res << endl; // search for endl considered dangerous. use '\n' instead.
}
return 0;
}

EDIT: removed wrong code.

so what you can use from this is don't use std::endl as it flushes the output after each write use '\n' instead.

Surt
  • 15,501
  • 3
  • 23
  • 39
0

I do not think you really need to improve the loop itself. What you should do is make use of mathematical properties of numbers, specifically of prime numbers. You should only loop up to the square root of the number. (See this question: Optimize calculation of prime numbers).

Here is my version of the code using the square root:

#include <cmath>
#include <iostream>

using namespace std;

int main() {
    long long inputs;
    cin >> inputs;

    for(long long j = 0 ; j < inputs ; ++j) {
        int divisors = 2;
        long long current, maxdiv;
        cin >> current;
        maxdiv = sqrt(current);

        for(long long i = 2 ; i <= maxdiv ; ++i)
            if(current % i == 0)
                divisors += 2;

        // If the square root is a divisor, we added one divisor too many above.
        if(maxdiv * maxdiv == current)
            --divisors;

        cout << divisors << "\n";
    }

    return 0;
}
mwk
  • 426
  • 7
  • 13
  • I forgot to say that I also optimized the output by using "\n" instead of std::cout to avoid flushing the output every time. – mwk Jul 23 '16 at 20:37
  • No problem. If this answer worked for you please consider accepting it. – mwk Jul 24 '16 at 19:03