WeavingBird1917 - 2 months ago 23

PHP Question

I'm trying to create a function to find the HCF of two values. I currently have a function that finds all the prime factors of each value and returns them in an array. To find the HCF, all that has to be done would be to compare the similar values in each array then multiply them together.

My code currently looks like this:

`function hcf($x, $y) {`

$hcf = array_product(array_intersect(prm_fac($x), prm_fac($y)));

if ($hcf != 0)

return $hcf;

else

return 1;

It's hard to explain, so I will show an example of the problem: If I try and find the HCF of 10 and 8, the prime factors of 10 will be 2, 5; the prime factors of 8 will be 2, 2, 2. The similar values in both arrays will be 2.

However, when I use the array_intersect function, it takes all the occurrences of 2, instead of just the single occurrence where it intersects. So instead of getting 2, I will get 2, 2, 2. How can I fix this problem?

Here is another example: I need to find the HCF of 4 and 16. The prime factors of 4 are 2, 2; the prime factors of 16 are 2, 2, 2, 2. I need to find the which values are the same for both arrays. If I use array_intersect on both arrays, it will give me 2, 2, 2, 2 instead of 2, 2. How do I fix this?

Here is the prm_fac function:

`function prm_fac($n) {`

$factors = array();

while ($n % 2 == 0) {

$factors[] = 2;

$n /= 2;

}

for ($i = 3; $i <= sqrt($n); $i += 2) {

while ($n % $i == 0) {

$factors[] = $i;

$n /= $i;

}

}

if ($n != 1)

$factors[] = $n;

return $factors;

}

Answer

Instead of `array_intersect`

you could use this custom function instead, which will take into account that values can repeat, but will only take them when they repeat as many times in both arrays.

The rest of your code can stay:

```
function common_values($a, $b) {
return array_filter($a, function($v) use (&$b) {
return ($i = array_search($v, $b)) !== false && ($b[$i] = -1);
});
}
```

So, call it like this:

```
function hcf($x, $y) {
$hcf = array_product(common_values(prm_fac($x), prm_fac($y)));
if ($hcf != 0)
return $hcf;
else
return 1;
}
```

Note that HCF is also known as GCD. See also this solution to get it in a more direct way, or use gmp-gcd from the GMP extension.