Hey so I'm making a factoring program and I'm wondering if anyone can give me any ideas on an efficient way to find what two numbers multiple to a specified number, and also add to a specified number.
for example I may have
(a)(b) = 6
a + b = 5
So essentially i just need a way to find the a and b values. In this case they would be 2 and 3.
Can anyone give me any ideas on where to start? Negative numbers must also be considered for use.
04 Answers
There is no need to loop, just use simple math to solve this equation system:
a*b = i;
a+b = j;
a = j/b;
a = i-b;
j/b = i-b; so:
b + j/b + i = 0
b^2 + i*b + j = 0
From here, its a quadratic equation, and it's trivial to find b (just implement the quadratic equation formula) and from there get the value for a.
There you go:
function finder($add,$product)
{ $inside_root = $add*$add - 4*$product; if($inside_root >=0) { $b = ($add + sqrt($inside_root))/2; $a = $add - $b; echo "$a+$b = $add and $a*$b=$product\n"; }else { echo "No real solution\n"; }
}Real live action:
0Here is how I would do that:
$sum = 5;
$product = 6;
$found = FALSE;
for ($a = 1; $a < $sum; $a++) { $b = $sum - $a; if ($a * $b == $product) { $found = TRUE; break; }
}
if ($found) { echo "The answer is a = $a, b = $b.";
} else { echo "There is no answer where a and b are both integers.";
}Basically, start at $a = 1 and $b = $sum - $a, step through it one at a time since we know then that $a + $b == $sum is always true, and multiply $a and $b to see if they equal $product. If they do, that's the answer.
Whether that is the most efficient method is very much debatable.
0With the multiplication, I recommend using the modulo operator (%) to determine which numbers divide evenly into the target number like:
$factors = array();
for($i = 0; $i < $target; $i++){ if($target % $i == 0){ $temp = array() $a = $i; $b = $target / $i; $temp["a"] = $a; $temp["b"] = $b; $temp["index"] = $i; array_push($factors, $temp); }
}This would leave you with an array of factors of the target number.
That's basically a set of 2 simultaneous equations:
x*y = a
X+y = b(using the mathematical convention of x and y for the variables to solve and a and b for arbitrary constants).
But the solution involves a quadratic equation (because of the x*y), so depending on the actual values of a and b, there may not be a solution, or there may be multiple solutions.
