1


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;
}
1
  • Maybe your prm_fac() function is not correct. Oct 29, 2016 at 12:37

2 Answers 2

0

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;   
}

Explanation of the function

array_filter($a, ...) iterates over every element of $a, and for each of them calls the function provided in the second argument. If that function returns a truthy value, the corresponding element will be included (and only then) in the array that is returned by array_filter.

That inner return value is calculated as follows:

($i = array_search($v, $b)) finds the index where the value ($v) from $a occurs in $b. This index is assigned to the variable $i (on-the-fly). Then its value is compared with false, which tells us whether there was a match or not. If not, the rest of the expression is not evaluated because the && can never make the total expression true again. And so the return value is false, i.e. this value from $a is excluded (because it does not occur in $b).

In the other case, $i will not be false but an integer index, so the first comparison is true. Then the next part of the && is evaluated:

($b[$i] = -1)

The matching value in $b is wiped out so to make sure it cannot match again in any next iteration. It is wiped out with a negative value, as factors are expected to be always positive, and non-zero values also are truthy so that the return value of array_filter is true, i.e. this value from $a must be included in the result.

Notes and refereces

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.

1
  • Added a section with explanation of the function.
    – trincot
    Oct 29, 2016 at 14:37
0

You can use array_unique() to remove duplicates from the result array returned from array_intersect().

I think it would be better if you remove duplicates from the prm_fac() array. Something like :

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

Best practice would be to write it in you prm_fac function itself -

 function prm_fac($val) {
    .
    .
    .
    return array_unique($factors);
 }

We can make use of foreach to get the actual product array - This works for the egs I tried.

$product = array();
$array1 = prm_fac($x); //return the unique $x values
$array2 = prm_fac($y); //return the unique $y values

foreach ($array1 as $val1) {
    foreach ($array2 as $val2) {
        // Form the product array if the iterated values are present in the other array
        if (in_array($val2, $array1) && in_array($val1, $array2)) {
            $product[] = $val1;
            $product[] = $val2;
        }
    }
}

Finally,

$hcf = array_product($product); //should give the proper product of values.
7
  • Yes, that would be the edge case, need to fix that, Maybe array_intersect is not the one that would help here Oct 29, 2016 at 12:55
  • The updated answer should work for the edge case discussed above Oct 29, 2016 at 13:20
  • I tried it with 8 and 10 but I got 64 as the HCF. I pasted the new function into the OP.
    – user6276743
    Oct 29, 2016 at 13:30
  • Heve you updated your prm_fac() function with array_unique as mentioned above ? Oct 29, 2016 at 13:34
  • When I added "return array_unique($factors);" directly into the prm_function, I get a result of 4 as the HCF of 8 and 10. I will put the whole code into the OP.
    – user6276743
    Oct 29, 2016 at 13:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.