ggT Primfaktoren vergleichen

[Tux]

Hallo,
ich bin gerade dabei, mir in PHP eine Funktion zu schreiben, die mir den größen gemeinsamen Teiler von $zahl1 und $zahl2 berechnet.
Dafür habe ich mir schon die zwei Funktionen primzahlen($größe_zahl) und   primfaktoren($zahl) geschrieben.

Ich bin soweit, dass ich für die Zahlen 25 und 15 beispielweise folgende Arrays bekomme:
Array {
  0 => 5
  1 => 5
}
Array {
  0 => 2
  1 => 5
}
hat jmd eine Idee, wie ich diese jetzt vergleichen und die gemeinsamen primfaktoren ausgeben könnte?

(Mein Chemieformelnrechner auf http://wurstbrot13.pytalhost.de/chemie.php )

[Benjamin]

Willst Du die Arrays vergleichen?
-> http://de3.php.net/manual/de/function.array.php
-> http://www.usegroup.de/software/phptutorial/arrays.html

[Tux]

Willst Du die Arrays vergleichen?

Jo, eigentlich schon, aber hald ein bisschen "anders" als die standard Vergleichfunktionen

-> http://de3.php.net/manual/de/function.array.php
-> http://www.usegroup.de/software/phptutorial/arrays.html

da hab ich nichts passendes gefunden, fällt dir eine ein?

-> ach, ich glaub ich mach meine Sache mit dem ggT anders:
Array {
  5 => 2
}
Array {
  2 => 1
  5 => 1
}
so geht's wahrscheinlich leichter.
Dann mach ich's wieder mit foreach schleife:
foreach($zahl1 as $teiler => $anzahl) {
  $zahl1[$teiler]-$zahl2[$teiler];
}

[Vinzenz Mai]

Hallo

-> ach, ich glaub ich mach meine Sache mit dem ggT anders:

willst Du nur den ggT? Wäre der Euklidische Algorithmus was für Dich?

Freundliche Grüße

Vinzenz

[Norbert]

Hallo,

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

<?php  
$z2 = 1576575;  /* erste Testzahl */  
$z3 = 1786785;  /* zweite Testzahl */  
/* nach der Zerlegung in Primfaktoren folgt */  
$A1 = array(3,5,7,7,11,13,17);  
$A2 = array(3,3,5,5,7,7,11,13);  
foreach($A1 as $val) {  
    if (in_array($val, $A2)) {  
        $erg = $val;  
    }  
}  
echo '<b>ggT</b> = '.$erg."\n";  
?>

Die einzige Bedingung ist, dass das zu iterierende Array aufsteigend
sortiert sein muss. Welches der beiden Arrays man durchwandert ist egal.

Gruss Norbert

[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