# programm zum berechnen des ggT und des kgV



## Sophielinchen (5. Juli 2007)

Hallo,

wir haben ne Aufgabe bekommen, dass wir das Programm für die Berechnung des ggT (größter gemeinsamer Teiler) und des kgV (kleinstes gemeinsames Vielfaches) von 3 Zahlen schreiben sollen. Für 2 Zahlen bekomm ich das ja hin...aber für 3? Kann mir da jemadn helfen?

Hier ist erst mal der Code für 2 Zahlen...wenn der denn überhaupt stimmt 


<html>
<head>
<title>ggt</title>
</head>
<body>

<h1>ggT</h1>


 <form action="ggt.php.php" method="post" target="">
 <input type="Text" name="zahla" value="" size="" maxlength=""></input>
 <input type="Text" name="zahlb" value="" size="" maxlength="">
 <input type="Submit" name="" value="berechne">
 </form>

 <?php

$a=$_POST["zahla"];
$b=$_POST["zahlb"];
  $c=$a;
  $d=$b;

$c!=$f;
 while ($c!=$d){
 if ($c>$d) {
  $c=$c-$d; }
 else {
 $d=$d-$c
 }

 }

 echo $c." ist der größte gemeinsame teiler und"
 $kgV=($a*$b)/$c;
 echo $kgV "ist das kleinste gemeinsame vielfache";

 ?>

</body>
</html>


----------



## Iches (5. Juli 2007)

So kann man es machen:


```
<form action='' method='post'>
Zahl 1: <input name='zahl0' type='text' value='<? echo $_POST[zahl0]; ?>' />
Zahl 2: <input name='zahl1' type='text' value='<? echo $_POST[zahl1]; ?>' />
Zahl 3: <input name='zahl2' type='text' value='<? echo $_POST[zahl2]; ?>' />
<input type='submit' value='Abschicken' name='gesendet' />
</form>
<?php
   if ($_POST[gesendet]) {
      $zahl[0] = $_POST[zahl0];
      $zahl[1] = $_POST[zahl1];
      $zahl[2] = $_POST[zahl2];
      $teiler = min($zahl);

      while (true){
         $sum0 =   bcmod($zahl[0],$teiler);
         $sum1 =   bcmod($zahl[1],$teiler);
         $sum2 =   bcmod($zahl[2],$teiler);
	 if ((empty($sum0) && empty($sum1) && empty($sum2)) OR $teiler == 1) 
            break;
         $teiler--;
      }
      $kgV = $zahl[0]*$zahl[1]*$zahl[2];
      echo "Der ggT ist: ".$teiler."<br />";
      echo "Der kgV ist: ".$kgV;
   }
?>
```

Nur ist es eigentlich kein ggT bzw. kgV mehr, weil dies eigentlich nur immer bei 2 Zahlen so ist.
Warum hast du denn bei dem kgV noch mal durch den ggT geteilt?


----------



## unknown_fool (5. Juli 2007)

```
$kgV = $zahl[0]*$zahl[1]*$zahl[2];
```
Hm, das stimmt so nicht. kgV steht für kleinstes gemeinsames Vielfaches... wenn wir jetzt 2, 3 und 4 haben, wäre das kgV 12 und nicht 24 (2*3*4). 

So ginge es (brute-force sozusagen, mir fiel nichts besseres ein ):

```
for($i = max($zahl);$found == false;$i++) {
 $found = true;
 foreach($zahl as $z) {
  if(is_float($i / $z)) {
   $found = false;
   break;
  }
 }
}
```
PS: _Das_ kgV, nicht der


----------



## Sophielinchen (5. Juli 2007)

Du kannst aber auch einfach schreiben 


```
$kgV = ($zahl[0]*$zahl[1]*$zahl[2])/$teiler;
```

So berechnet man zumindestens das kgV .... also kgV (x,y,z)= (x*y*z)/ ggT (x,y,z)

So stehts im Tafelwerk =)


----------



## Iches (5. Juli 2007)

Warum du musst doch beim kgV alle zusammen rechnen, weil sonst hast du ja sozusagen nicht alle Zahlen miteinander kombiniert. Ach ist ja auch egal. Das braucht man eigentlich sowiso nicht mehr (denk ich mal)


----------



## mewX (5. Juli 2007)

Sowas hab ich irgendwann schonmal gemacht , da:
http://www.ptec-media.de/prog/primfak.php
Sorce-Code:
http://www.ptec-media.de/prog/primfak.php.txt
(ein bisschen aufwendig )

EDIT: Achso, 3 Zahlen  Mal sehen ob man das einfach abändern kann...


----------



## pucawo (11. Juli 2011)

*Stein'scher Algorithmus zur Berechnung des ggT*

Auch wenn der letzte Eintrag schon ne Weile her ist, so rankt diese Seite doch sehr gut. Daher füge ich noch meinen Senf hinzu. Die folgende Funktion zur Berechnung des ggT entspricht dem Stein'schen Algorithmus. Das heißt unheimlich schnell und Ressourcen-sparend:


```
function ggT($a, $b)
{
    if($a==0)
    {
        return $b;
    }
    $k=0;
    while($a%2===0 && $b%2===0)
    {
        $a = $a / 2;
        $b = $b / 2;
        $k++;
    }
    if($a%2==1)
    {
        $t = -$b;
    }
    else
    {
        $t = $a;
    }
    while($t !== 0)
    {
        while($t%2===0)
        {
            $t = $t / 2;
        }
        if($t > 0)
        {
            $a = $t;
        }
        else
        {
            $b = -$t;
        }
        $t = $a - $b;
    }
    return $a * pow(2, $k);
}
```


Noch eine kurze Anmerkung zum Zusammenspiel zwischen kgV und ggT:

ggT(k_1,...,k_n) * kgV(k_1,...,k_n) = k_1 * ... * k_n


----------



## pucawo (11. Juli 2011)

*Euklid'scher Algorithmus zur Berechnung des ggT*


```
function euclid($a, $b)
{
    if($b == 0)
    {
        return $a;
    }
    else
    {
        return euclid($b, $a%$b);
    }
}
```


----------

