2
\$\begingroup\$

Inputs are two values \$1 \le m , n \le 10^{12}\$. I don't know why my code is taking so long for large values where the time limit is 1 sec. Please suggest some critical modifications.

#include <iostream>
#include<algorithm>
using namespace std;

int main() {
    long long count = 0, m, n;
    cin >> m >> n;

    for (long long int i = 1; i <= ((min(m, n)) / 2) + 1; i++) {
        if ((m%i == 0) && (n%i == 0)) {
            count++;
        }
    }

    if (((n%m == 0) || (m%n == 0)) && (n != m)) {
        count++;
    }

    cout<<count;

    return 0;
}
\$\endgroup\$
5
  • \$\begingroup\$ @kyrill Looks like a more math oriented approach (logarithmic as done with good ole slide rulers) could help to improve performance, instead of the (naive) brute force approach. (Remember that python question recently?). But I'm weak at math :-/. Also the matching factors should be determined for one of the numbers 1st, and then checked for the 2nd one for counting. \$\endgroup\$ Apr 19 '17 at 1:23
  • \$\begingroup\$ ^^^ That's the best pointer I can give. @AshutoshMalla \$\endgroup\$ Apr 19 '17 at 1:27
  • 3
    \$\begingroup\$ Please note reviewers are always free to comment on any & all aspects of the code. Note that this includes poor indentation and readability. If this is a Project Euler solution, you should edit the problem statement into the question and state the problem number, so that users who want to avoid spoilers don't stumble on this Q&A by accident. \$\endgroup\$ Apr 19 '17 at 1:52
  • 1
    \$\begingroup\$ Every common factor of \$m,n\$ also divides their \$\gcd\$. Compute \$k = \gcd(m,n)\$, and then find all factors of \$k\$. \$\endgroup\$
    – vnp
    Apr 19 '17 at 2:14
  • \$\begingroup\$ Don't use using namespace std \$\endgroup\$
    – Nykakin
    Apr 19 '17 at 9:26
3
\$\begingroup\$
    long long count = 0, m, n;
    ...
    for (long long int i = 1; i <= ((min(m, n)) / 2) + 1; i++) {

long long or long long int? I'm not a C++ programmer so I don't know whether style guides have a preference, but I'm quite certain that you should be consistent.


Inputs are two values \$1 \le m , n \le 10^{12}\$. I don't know why my code is taking so long
...

   for (long long int i = 1; i <= ((min(m, n)) / 2) + 1; i++) {

There you go. The main loop runs up to \$5 \times 10^{11}\$ times. As a rule of thumb, when brute-forcing a problem I work on the basis that \$10^9\$ is about as high as I want to go.

Solution: change your algorithm. This will require learning some mathematics, and I'm not going to write a detailed tutorial, but there are two things you need:

  1. Basic number theory: unique prime factorisation, greatest common divisor, finding it efficiently;
  2. Sane factorisation of a small number (and \$10^{12}\$ is very small in these terms)

If you wanted to do it properly then you could extend the number theory research and learn about Euler's totient function.

\$\endgroup\$
2
  • \$\begingroup\$ Thank u soo much everyone , i did some research and used a gcd approach and it worked like a charm . \$\endgroup\$ Apr 19 '17 at 10:34
  • \$\begingroup\$ long long or long long int : Since you know the range of numbers you need, std::int_fast64_t would be preferred. \$\endgroup\$
    – JDługosz
    Jun 30 '21 at 22:49
2
\$\begingroup\$

Don't pull the (large, and expanding) set of identifiers from std into the global namespace. It doesn't even reduce the source size here.

long long int might not be the best type to use; depending on the platform, long int may be sufficient. And we're only using positive values. I recommend std::uint_fast64_t as a better choice.

Instead of std::min(m,n), it may be helpful to start with a conditional std::swap so that we know which is larger and which is smaller from that point onwards.

The algorithm is unreasonably slow (billions of trial divisions). A much more performant technique is:

  1. Find the greatest common divisor (GCD) of the two numbers, thus eliminating the non-common factors.

    \$ s = gcd(m,n) \$

  2. Perform the prime factorisation of the GCD.

    \$ \prod{p_i^{e_i}} = s \$

  3. Compute the number of combinations of that prime factorisation.

    \$ f(m,n) = \prod{(e_i+1)} \$

\$\endgroup\$
3
  • \$\begingroup\$ signed ints are faster, so I disagree. Only use unsigned when you need the bit representation, need wrap-around to be defined, or really need that extra one bit of range. Just because your domain is non-negative is not a proper reason. \$\endgroup\$
    – JDługosz
    Jun 30 '21 at 22:52
  • 1
    \$\begingroup\$ That's a blanket claim, and depends very much on the code, the target architecture and the compiler. I believe in coding for readability and obvious correctness before benchmarking and (when necessary) micro-optimising. \$\endgroup\$ Jul 1 '21 at 4:44
  • \$\begingroup\$ Even before the modern compiler optimizers that allow signed to be faster, the expert consensus was that using unsigned for non-negative domains was wrong. Implicit conversions allow a negative number to be passed in silently, which would turn into a large positive number. It doesn't stop you from passing negative numbers, but rather stops you from testing for that. Current: github.com/isocpp/CppCoreGuidelines/blob/master/… and github.com/isocpp/CppCoreGuidelines/blob/master/… \$\endgroup\$
    – JDługosz
    Jul 1 '21 at 13:46
1
\$\begingroup\$

Don’t write using namespace std;.

You can, however, in a CPP file (not H file) or inside a function put individual using std::string; etc. (See SF.7.)


Does m and n change? I think not; you are just looping through all values of i, right? Put the work in a separate function, and these parameters can be const. That will make it easier to read and understand.

In general, separate out input, the real work, and output.


Division (and modulo) is dog slow on most CPUs. On the x86 chips, for example, you can look at Agner Fog's charts on the internal resources used for each operation. Besides having a long latency and taking a lot of cycles, on the chips I looked at (e.g. Broadwell) it uses a great many of the dispatch ports. So, it also clogs up the internal resources and prevents instruction-level parallelism from filling in the long latency.

Since you are incrementing i, incrementally adjust the result of the modulo as well. That would be about a hundred times faster than the % I would think (ballpark).

You evaluate ((min(m, n)) / 2) + 1 each time through. Does the optimizer figure out that this never changes? If you used const (see above) I think it would have a better chance of doing so for you. But, you should just precalculate end yourself and it makes the loop more readable too.

\$\endgroup\$
3
  • \$\begingroup\$ "Does the optimizer figure out that this never changes?" - Yes, yes they do, all of them, without fail, every time. Don't waste your time and make the code less readable by moving it out. This is as trivial as optimization a compiler does. \$\endgroup\$
    – Emily L.
    Jul 2 '21 at 11:22
  • \$\begingroup\$ Writing the end bounds on a separate line makes it more readable in this case. \$\endgroup\$
    – JDługosz
    Jul 2 '21 at 14:06
  • \$\begingroup\$ Also note that the speed of the idiv instruction is not the reason why this code is slow and heading down that path of optimization is fruitless and bringing that up here is misleading. The problem with the code is that it's using a brute force algorithm where another algorithm is required, see Toby's answer. \$\endgroup\$
    – Emily L.
    Jul 4 '21 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.