ggT Primfaktoren vergleichen

[Christian Seiler]

Hallo Norbert,

wenn man davon ausgeht, dass die Primfaktoren als Array vorliegen,
funktioniert das wie folgt:

Nichts für ungut, aber das liefert Dir nur den größten Primteiler, nicht den größten gemeinsamen Teiler. Der ist nämlich das Produkt aller (!) gemeinsamen Primteiler in der korrekten Multiplizität.

Wenn man davon ausgeht, dass die Ursprungsarrays in der korrekten Multiplizität vorliegen, dann wäre folgender Code zielführend:

<?php  
function intersect_multiplicity ($first, $second) {  
  $intersect = array_intersect (array_unique ($first), array_unique ($second));  
  $result = array ();  
  foreach ($intersect as $item) {  
    $count = min (count (array_keys ($first, $item)), count (array_keys ($second, $item)));  
    for ($i = 0; $i < $count; $i++) {  
      $result[] = $item;  
    }  
  }  
  return $result;  
}  
  
$A1 = array(3,5,7,7,11,13,17);  
$A2 = array(3,3,5,5,7,7,11,13);  
  
// zum test auch die Zahlen aus den Primfaktoren berechnen  
$zahl1 = array_product ($A1);  
$zahl2 = array_product ($A2);  
$ggt = array_product (intersect_multiplicity ($A1, $A2));  
  
echo "ggt ($zahl1, $zahl2) = $ggt\n";  
  
?>

Allerdings: Der euklidische Algorithmus ist da sowohl DEUTLICH einfacher als auch DEUTLICH schneller.

Viele Grüße,
Christian