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\$
  • \$\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
  • 2
    \$\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\$ – Mathieu Guindon Apr 19 '17 at 1:52
  • \$\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
1
\$\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\$
  • \$\begingroup\$ Thank u soo much everyone , i did some research and used a gcd approach and it worked like a charm . \$\endgroup\$ – Ashutosh Malla Apr 19 '17 at 10:34

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.