Find the no of pairs whose sum divides the product from 0 - 1000000000 I have designed the code but the problem is it timeouts as the range is 1000000000 but works fine with 1000. Any idea to optimize this or a mathematic logic for it? I just need to find the no of pairs(a,b) such that a &lt; b and a*b % a+b == 0 if a range is given, 
eg: 15 - o/p 4 as (3,6)(4,12)(6,12)(10,15).

php code:

$count = 0;
$no = 1000;
for($b = 1; $b &lt;= $no; $b ++) {
    for($a = 1; $a &lt; $b; $a ++) {
        $sum = $a + $b;
        $prod = ($a * $b);

        if (($prod % $sum == 0) {
            ++ $count;
        }
        $arr [$b] = $count;
    }
}

echo '&lt;pre&gt;';
print_r($arr);
echo '&lt;pre&gt;';


I need some math logic to get no of pairs rather performing actual process as above. If I found a relation or expression for this then actual process is not required.
These kind of puzzles have to be solved by first analyzing the problem.
If you look at the samples that you have already found you will notice that in all samples the two numbers share a rather large common factor. This makes sense, since if a and b have a common factor then both a+b and a*b are divisible by this common factor, which increases the probability that a+b divides a*b. So let's try to find out more formally when (a,b) is a good pair:

Let g=gcd(a,b). Then there exist integers r,s with

a = r * g
b = s * g


Then 

a + b = (r+s)*g
a * b = r*s*g^2


Thus a+b divides a*b if (r+s)*g divides r*s*g^2 and hence if r+s divides r*s*g.
Also since g is the greatest common divisor it follows that r and s have no divisor in common (i.e. gcd(r,s)=1). From Euclid's algorithm follows that gcd(r+s,r) = 1 and 
gcd(r+s, s) = 1 and hence also gcd(r+s, r*s) = 1. Thus if r+s divides  r*s*g then 
r+s must divide g.

Thus all the good pairs below a bound N can be described as follows:
If r,s,k are integers such that 1 &lt; r &lt; s &lt; N^0.5, gcd(r,s)=1 and s * (r + s) * k &lt;= N then (a,b) = (r * (r + s) * k, s * (r + s) * k) is a good pair.

Implementing this isn't hard. Running the algorithm up to 10^9 takes a few minutes (depending on the programming language).

One big question remains: Why on earth has the problem been migrated to "Code review"?