I need to find out the fastest way to count nested loops. I am adding 3 numbers , the final number is wanted result. For better explanation here is example   read number 1   read number 2   read final number 3There are 17 ways how to achieve 500 with those two numbers e.g 10*2 + 15*32and so on , the code for this is pretty simple i_max=final_number/number1 j_max=final_number/number2for(i=0;i<i_max;i++){     for(j=0;j<j_max;j++){             count=number1 * i;              count_two = number 2 * j;               if(count+count_two==final_number){                    //print it}}}This code works fine , but the problem is when i input large numbers likenumber1=100number2=500final_number=50000000in this case , the computer takes very long time to count/find/print all possible ways. Is there any way to make alghoritm for this as fast for big numbers too? I have found out that the  better way and fastest is not to increment i by 1 but by whole number or whole number /2 and sometimes both of them ; but how can i decide if i should add whole number or just half of the number to the i/j?I tred to write in as much in pseudo code as i couldAlso , i find out the second loop does not have to start always from 0/max number everytime it gets triggered , so for i=0 ; i<max_number1;i++  for j=max_number2;j>=0;j--    if number1*i + number2*j == final number     max_number 2 = jBut i still fail to find when should i add whole number and when just half of it, I tried to increment first number by half of number2 , and second number by 1 until it finds match and then adding whole numbers , but this didnt work as i expectedit worked for larger numbers but for numbers like1013100it said there is now way to combine first two and make 100 while there is a one10 * 10 + 13 * 0On request / for those who got lost in my explanation = i input 3 random numbers e.g1013749and i want to find out how many combinations of first two nubmers1013would get result 749it made it with nested loopsfor(j=0;j<j_max;j++){                 count=number1 * i;                 count_two = number 2 * j;                   if(count+count_two==final_number){                        //print it    }    }}which works but takes very long time to calculate if i input large numbers , for things i have tried or come up with read whole post.Full example =number 1=757number 2=989final number =  56899148There is 77 way how to combine first two numbers into the final one and those are757 * 0 + 989 * 57532 757 * 989 + 989 * 56775 757 * 1978 + 989 * 56018 757 * 2967 + 989 * 55261 757 * 3956 + 989 * 54504 757 * 4945 + 989 * 53747 757 * 5934 + 989 * 52990 757 * 6923 + 989 * 52233 757 * 7912 + 989 * 51476 757 * 8901 + 989 * 50719 757 * 9890 + 989 * 49962 757 * 10879 + 989 * 49205 757 * 11868 + 989 * 48448 757 * 12857 + 989 * 47691 757 * 13846 + 989 * 46934 757 * 14835 + 989 * 46177 757 * 15824 + 989 * 45420 757 * 16813 + 989 * 44663 757 * 17802 + 989 * 43906 757 * 18791 + 989 * 43149 757 * 19780 + 989 * 42392 757 * 20769 + 989 * 41635 757 * 21758 + 989 * 40878 757 * 22747 + 989 * 40121 757 * 23736 + 989 * 39364 757 * 24725 + 989 * 38607 757 * 25714 + 989 * 37850 757 * 26703 + 989 * 37093 757 * 27692 + 989 * 36336 757 * 28681 + 989 * 35579 757 * 29670 + 989 * 34822 757 * 30659 + 989 * 34065 757 * 31648 + 989 * 33308 757 * 32637 + 989 * 32551 757 * 33626 + 989 * 31794 757 * 34615 + 989 * 31037 757 * 35604 + 989 * 30280 757 * 36593 + 989 * 29523 757 * 37582 + 989 * 28766 757 * 38571 + 989 * 28009 757 * 39560 + 989 * 27252 757 * 40549 + 989 * 26495 757 * 41538 + 989 * 25738 757 * 42527 + 989 * 24981 757 * 43516 + 989 * 24224 757 * 44505 + 989 * 23467 757 * 45494 + 989 * 22710 757 * 46483 + 989 * 21953 757 * 47472 + 989 * 21196 757 * 48461 + 989 * 20439 757 * 49450 + 989 * 19682 757 * 50439 + 989 * 18925 757 * 51428 + 989 * 18168 757 * 52417 + 989 * 17411 757 * 53406 + 989 * 16654 757 * 54395 + 989 * 15897 757 * 55384 + 989 * 15140 757 * 56373 + 989 * 14383 757 * 57362 + 989 * 13626 757 * 58351 + 989 * 12869 757 * 59340 + 989 * 12112 757 * 60329 + 989 * 11355 757 * 61318 + 989 * 10598 757 * 62307 + 989 * 9841 757 * 63296 + 989 * 9084 757 * 64285 + 989 * 8327 757 * 65274 + 989 * 7570 757 * 66263 + 989 * 6813 757 * 67252 + 989 * 6056 757 * 68241 + 989 * 5299 757 * 69230 + 989 * 4542 757 * 70219 + 989 * 3785 757 * 71208 + 989 * 3028 757 * 72197 + 989 * 2271 757 * 73186 + 989 * 1514 757 * 74175 + 989 * 757 757 * 75164 + 989 * 0Again this works , but with very big numbers it takes lot of time to actually calculate it.
fastest counting of nested loops
algorithms;counting
With inputs $n_1,n_2,n_3$, you want to find all positive integers $(a,b)$ such that $an_1+bn_2 = n_3$ You observed that for even moderately large inputs, your two nested loops with a test to see if you come up with a solution takes a long time. It you apply a bit of number theory, there's an algorithm that is very much faster.First, find the greatest common divisor of $n_1$ and $n_2$. The extended euclidean algorithm is not only very fast (using a number of steps proportional to the number of digits in the larger of the two numbers), but also provides a way to do the next step. If $g=\gcd(n_1,n_2)$ divides $n_3$, continue to the next step, otherwise there will be no solutions to your problem, so quit.The extended Euclidean algorithm will give you integer solutions, $a, b$ to$$an_1+bn_2=g$$In what follows, we'll assume $g=1$ for simplicity. If it's not, just divide $n_1,n_2,n_3$ by $g$ and carry on as below. We'll then have$$(an_3)n_1+(bn_3)n_2 = n_3$$ You're getting close to a solution, but $an_3$ or $bn_3$ might not both be positive, so we'll need some other solution. Observe that for any integer $k$,$$\begin{align}& (an_3-kn_2)n_1+(bn_3+kn_1)n_2\\=&\ (an_3)n_1-kn_2n_1+(bn_3)n_2+kn_1n_2\\=&\ (an_3)n_1+(bn_3)n_2 = n_3\end{align}$$so $an_3-kn_2$ and $bn_3+kn_1$ will also be solutions, for any integer $k$.Now all we have to do is pick $k$ values such that$$an_3-kn_2\ge 0\quad\text{and}\quad bn_3+kn_1\ge 0$$In other words, all we have to do is loop through the integers $k$ such that$$-\frac{bn_3}{n_1}\le k\le\frac{an_3}{n_2}$$Edit: There's a potential problem here, though: it might be that some of the intermediate calculations might be too large to avoid integer overflow. Let's see if we can keep everything no larger than $n_3$. We could let $k=a\lfloor n_3/n_2\rfloor$ and it's not hard to show that $$a'=an_3-kn_2=an_3-a\left\lfloor\frac{n_3}{n_2}\right\rfloor n_2>0$$and then let$$b'=\frac{n_3-a'n_1}{n_2}$$we will have found a solution, $(a',b')$ to$$a'n_1+b'n_2=n_3$$which was our goal.Here's how it would work for an example almost like yours with $n_1=989$, $n_2=757$, $n_3=56899150$.First, find $\gcd(989,757)=1$, and we find from the extended Euclidean algorithm that$$1=(62)989+(-81)757$$so we let $$\begin{align}a'&=62\left(56899150-757\left\lfloor\frac{56899150}{757}\right\rfloor\right)\\  &= 62(56899150-757\cdot75164)\\  &= 62(56899150-56899148)\\  &= 62\cdot 2 = 124\end{align}$$and we also find that $b'=75002$, so we'll have solutions $(a',b')$ given by$$\begin{array}{cc}a' & b'\\124 & 75002 \\881 & 74013 \\1638 & 73924 \\\vdots & \vdots \\56899 & 827\end{array}$$where each row in the solution is the previous row solution for $a'$ plus 757 and the previous row solution for $b'$ minus 989, stopping when the $b'$ solution is negative.