We will start by reinforcing some of the things already mentioned in the other answers.
First, do not use the header <bits/stdc++.h>
. This has been addressed before on SO in the question Why should I not #include bits/stdc++.h?. Also, using namespace blah
is bad practice, regardless of the library/header you are referring to (doesn't have to be std
). This too has been addressed on SO in the question Why is “using namespace std” considered bad practice?. Lastly, the overall spacing and naming you have chosen is not very clear, which leads to difficult code readability.
Now, to address the specific problem of finding pairs of numbers in a given range that have a specific LCM and GCD: The code you have provided is not correct.
I believe that one of the best methods for deriving a correct algorithm is by looking at a well-formed example. How do they go about doing that (especially the well-formed part)?
A good place to start is by looking at the definitions associated with our problem and try to find a relationship that we can build off of. As @esote points out in the comments, we are given the property:
$$ \gcd(a, b) \cdot \textrm{lcm}(a, b) = |a \cdot b| $$
Continuing with our well-formed mission, we want to pick our numbers such that we get a decent number of hits. This means that we should avoid cases that we know will give bad results, such as cases:
- \$\gcd(n_1,n_2) > \textrm{lcm}(n_1, n_2)\$
- \$n_1,n_2 > \textrm{lcm}\$
- \$n_1,n_2 < \gcd\$
And many more. We should also look for numbers that have many divisors as this is likely to increase the number of hits. Highly composite numbers are great candidates for this.
Let's set gcd = 12
, lcm = 720720
, n1 = 100
, and n2 = 7000
to see what happens. With this setup, a correct algorithm should return at least 9, if order doesn't matter, which I think should be the case (I agree with @PeterTaylor when he states "but I would think that unordered are slightly more likely to be the intent.").
The 9 pairs are:
1260, 6864
1584, 5460
1680, 5148
1716, 5040
1872, 4620
1980, 4368
2340, 3696
2640, 3276
2772, 3120
It looks like we have found a good example to build our algorithm off of (I will leave it to the reader to prove that these are the only numbers in the given range where \$\gcd = 12\$ and \$\textrm{lcm} = 720720\$). We note that running the OP's algorithm on the example above returns 0
.
What are some take-aways from the 9 pairs above? For starters, the suggestion by @JerryCoffin for finding the starting point is good, but we can do much better. According to the method proposed by @JerryCoffin, our starting point would be 108 as it is the first number greater than or equal to 100 that is also divisible by 12. As you can see from the 9 pairs above, the smallest number encountered is much larger than 108 (i.e. 1260).
Why is this? Rearranging the relationship above, we have (given \$a < b\$):
$$ a = \frac{\gcd(a, b) \cdot \textrm{lcm}(a, b)}{b} $$
Which means that the smallest value of \$a\$ is:
$$ \frac{12 \cdot 720720}{7000} \approx 1235 $$
If a < 1235
, we can see that that the corresponding value for b
would exceed 7000. Now, using the method mentioned by @JerryCoffin of making the starting point divisible by our GCD, we see that 1236 satisfies this condition and should be our starting value.
What about our maximum value? This can be attacked by noticing that we start getting repeated values after we have crossed the threshold:
$$ \sqrt{\gcd \cdot \textrm{lcm}} $$
For example, had we continued on after 2772
above (the last value in the left column), we would have simply obtained 3120, 2772
followed by 3276, 2640
, ... 6864, 1260
, which is exactly what we already have but in reverse. Now we note that:
$$ 2772 < \sqrt{12 \cdot 720720} \approx 2940 $$
Thus, 2940
will be our ending value.
For our incrementing value, we take the suggestion by @Jerry and use the GCD. Using all of this information together with the algorithm for GCD suggested by @esote, we have the following:
#include <iostream> // For cout, cin, & endl
#include <cmath> // For sqrt, ceil, min, & max
int myGCD(int u, int v) {
int r;
while (v != 0) {
r = u % v;
u = v;
v = r;
}
return u;
}
int numPairs(int n1, int n2, int lcm, int hcf) {
int count = 0;
int myProd = lcm * hcf;
// If sqrt(myProd) > n2, then we need to stop at n2
int myLim = std::min((int) std::sqrt((double) myProd), n2);
// We ensure that we cover the entire range by taking the
// max. E.g. if n1 > myProd / n2, we would start at n1
double myStart = std::max(n1, myProd / n2);
myStart = std::ceil(myStart / (double) hcf) * hcf;
for (int i = (int) myStart; i <= myLim; i += hcf)
if (lcm % i == 0) // ensure our number is divisible by lcm
if (myGCD(i, myProd / i) == hcf) // ensure our pair gives correct gcd
++count;
return count;
}
int main() {
int n1, n2, lcm, hcf, cnt;
std::cin >> n1 >> n2 >> lcm >> hcf;
cnt = numPairs(n1, n2, lcm, hcf);
std::cout << cnt << std::endl;
return 0;
}
Running this for the given example promptly returns 9 (here is an ideone link with working code).
Figuring out why OP's algorithm returns bad results:
In the OP's algorithm, it returns 0 because of the following line:
int a = lcm/i;// its other multiplier
This should be int a = hcf * lcm / i;
. We should also note that this calculated value for a
may exceed n2
or fall below n1
. To fix this, all we need to do is add a check before the line if(b == hcf){
like so:
if (a <= n2 && a >= n1) {
if (b == hcf) {
While we are at it, we can save a call to gcd
by placing it inside the new condition we added:
if (a <= n2 && a >= n1) {
int b = gcd(a,i);
if (b == hcf) {
When we run the new modified OP's code, we obtain 18 as expected (OP is double counting pairs with same values but different orders: here is another ideone link with the fixes).
Benchmarks:
Putting both algorithms in the same file and running the main
function below, we see that the modified algorithm is over 7000x
faster.
#include <ctime>
.
. // more code here
.
int main() {
int n1, n2, lcm, hcf, countNoOrder = 0, countAll = 0;
std::cin >> n1 >> n2 >> lcm >> hcf;
std::clock_t start_time, end_time;
start_time = clock();
for (int i = n1; i < (n1 + 500); ++i)
countNoOrder += numPairs(i, n2, lcm, hcf);
end_time = clock();
std::cout << "Time taken with modified algorithm numPairs : " <<
end_time - start_time << std::endl;
start_time = clock();
for (int i = n1; i < (n1 + 500); ++i)
countAll += OPAlgo(i, n2, lcm, hcf);
end_time = clock();
std::cout << "Time taken with corrected OP algorithm : " <<
end_time - start_time << std::endl;
std::cout << "Result for modified algo : " << countNoOrder << std::endl;
std::cout << "Result for original OP code : " << countAll << std::endl;
return 0;
}
And with the input given as : 10000 500000 8648640 120
, we obtain the following:
Time taken with modified algorithm numPairs : 408
Time taken with corrected OP algorithm : 3006723
Result for modified algo : 3000
Result for original OP code : 6000
Which gives 3006723 / 408 = 7369.41...
supporting our claim above (i.e. more than 7000x
faster) Here is a link to ideone which shows the benchmarking code.