primfaktorzerlegung

lima-city → Forum → Programmiersprachen → PHP, MySQL & .htaccess

Autor dieses Themas
xasa

xasa hat kostenlosen Webspace.

23:03, 30.5.2007
hallo leute

ich suche ein kleines Programm (soll nicht zu kompliziert sein und basierend auf PHP-Grundlagen), welches die Primfaktorzerlegung einer Zahl (Bsp: 100) elegant darstellt.
Mit elegant meine ich, dass es falls es z.b. 2 mal 2 wäre, dass es "2 hoch 2" ausschreibt.
Ach ja, und die Malpunkt könnt ihr mit "x" oder "." oder "," darstellen.

Ich hoffe ihr könnt mir helfen.
Ich krieg das nicht auf die Reihe, also wenns geht dann heute noch ;)!

mfg
xasa
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!

lima-city: Gratis werbefreier Webspace für deine eigene Homepage
andieo

andieo hat kostenlosen Webspace.

23:09, 30.5.2007
soll das jetzt in php sein oder was? Weil elegant darstellen passt eher zu basic
Autor dieses Themas
xasa

xasa hat kostenlosen Webspace.

23:12, 30.5.2007
ja es soll mit PHP gemacht werden. Ich weiss, mit Basich gehts scho besser, aber diesmal ist PHP gefragt. Ich hoffe das geht auch;).
keiax

keiax hat kostenlosen Webspace.

23:38, 30.5.2007

xasa schrieb:
ja es soll mit PHP gemacht werden. Ich weiss, mit Basich gehts scho besser, aber diesmal ist PHP gefragt. Ich hoffe das geht auch;).

Der Algorithmus ist der gleiche ... nur die Variablen schauen eben etwas anderst aus.
Der Algo ist da beschrieben und eigentlich recht simpel:
http://www.arndt-bruenner.de/mathe/scripts/primzahlen.htm#1a
und nachdem ich deine Faulheit nicht unterstützen will sollte dir dass erstmal reichen um ein PHP Script zu programmieren ...
Wenn du dann an einer Stelle nichtmehr weiter weisst kannst du dich ja wieder bemerkbar machen

Beitrag geaendert: 30.5.2007 23:39:21 von keiax

3:16, 31.5.2007

<?php
    //Algorithmus zum Bestimmen von Primzahlen bis zu einer bestimmten Zahl nach Eratosthenes
  function eratosthenes($max) {
    $sieve = array_fill(2, ($max-1), false);
    while ($key = array_search(false, $sieve)){
      $sieve[$key] = true;
      for ($i=$key*$key; $i<=$max; $i+=$key){
        if (array_key_exists($i, $sieve)){
          unset($sieve[$i]);
        }
      }
    }
    return array_keys($sieve);
  }
    //Irgendeine natuerliche Zahl, die in ihre Primfaktoren zerlegt werden soll
  $nZahl = 89564;
    //Zwischenvariable
  $Zahl  = $nZahl;
    //Alle Primzahlen bis vorlaeufig 300
  $pZahl = eratosthenes(300);
    //Array mit den endgueltigen Primfaktoren
  $pRes  = array();
    //Zahlvariable fuer die Schleife initialisieren
  $i = 0;
    //Schleife, die solange die Zahl in ihre Faktoren zerlegt, bis eins herauskommt
  while($Zahl != 1){
      //Existiert die Primzahl
    if(isset($pZahl[$i])){
        //Ist die Zahl durch die aktuelle Primzahl zu teilen,
      if(($Zahl % $pZahl[$i]) === 0){
          //wird das neue Ergebnis eingelesen
        $Zahl   = $Zahl / $pZahl[$i];
          //und der Faktor im Array hinzugefuegt
        $pRes[] = $pZahl[$i];
      }
        //Andernfalls wird einfach nur die Zaehlvariable inkrementiert und somit die naechste Primzahl gewaehlt
      else
        $i++;
    }
    else{
        //oder muss das Array noch erweitert werden?
      $pZahl = eratosthenes($pZahl[$i-1]+$pZahl[$i-1]);
    }
  }
    //Ausgabe
  $string = $nZahl.' = ';
  foreach($pRes as $key=>$value)
    $string .= $value.'*';
  print substr($string,0,strlen($string)-1);
?>

Der Code ist ziemlich umständlich, da bei sehr großen Zahlen immer wieder ein neues Array generiert werden muss. Mit einer Funktion, die einfach die nächste Primzahl findet, wie gmp_nextprime aus der GMP-Bibliothek, wäre es einfacher und vor allem schneller...

Beitrag geaendert: 31.5.2007 3:23:27 von spacke

scout

scout hat kostenlosen Webspace.

9:37, 31.5.2007
wow cooler Algorithmus um Primzahlen zu bestimmen.
Kannte ich bisher noch nicht.
Danke Spacke

Grüßle
Autor dieses Themas
xasa

xasa hat kostenlosen Webspace.
15:02, 31.5.2007
eine Alternative zum obigen Quelltext.
```
<?php

$a=100;
$b=2;
$i=0;
print $a."= "; 
while ($a>1)
{
	if(($a%$b)==0)
	{
		print $b."*";
		$a=$a/$b;
		$b=2;
	}
	else
	
	{
		$b++;
	}
}

?>
```
Man sieht dann auf dem Bildschirm: 100=2*2*5*5

Ich will aber, dass es das schreibt: 100=2^2*5^2

spacke

spacke hat kostenlosen Webspace.

16:57, 31.5.2007

<?php
  $nZahl = 100;
  $pZahl = 2;
  $pRes  = array();
  $i = 0;
  print $nZahl.' = ';
  while ($nZahl>1){
    if(($nZahl%$pZahl)==0){
      $nZahl=$nZahl/$pZahl;
      $pRes[$pZahl]++;
    }
    else
      $pZahl++;
  }
  $text = false;
  foreach($pRes as $key => $value){
    $text.= ($value>1)? $key.'^'.$value.'*':$key.'*';
  }
  print substr($text,0,strlen($text)-1);
?>

Tadaa! ;)
Ausgabe:

100 = 2^2*5^2

Hier zu sehen:
http://spacke.omegaspace.de/primzahlen.php

Beitrag geaendert: 31.5.2007 17:27:37 von spacke

Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!

lima-city: Gratis werbefreier Webspace für deine eigene Homepage

Dir gefällt dieses Thema?

Über lima-city

lima-city bietet dir kostenlosen und werbefreien Speicherplatz für Deine Homepage. Sofort anmelden und direkt loslegen mit Webspace, PHP, Datenbanken, günstigen Domains und einer tollen Community!

kostenloser Webspace werbefrei: lima-city