Fermat-Methode, Lehman-Methode Selbstversuch

[macbest]

Hallo,

habe mal versucht die Fermat und die Lehmann-Methode selbst zu implementieren, hat leider nicht so richtig funktioniert. Wäre toll, wenn sich mal jemand meinen Quellcode anschauen könnte. Habe nur die relevanten Teile gepostet.

Fermat:



<?php

if (!empty($_POST['n']) && is_numeric($_POST['n'])) {
rechne($_POST['n']);
}

function rechne($n) {
$c=0;
for ($a=ceil(sqrt($_POST['n'])); $a<=($_POST['n']+9)/6; $a++) {
if (is_int(sqrt($a*$a-$_POST['n']))){
echo $a-sqrt($a*$a-$_POST['n']) . "<br>";
$c=1;
}
}

if ($c==0){
echo $_POST['n'] . "ist Primzahl";
}
}

?>


Lehman



<?php
if (!empty($_POST['n']) && is_numeric($_POST['n'])) {
faktorisierung($_POST['n']);
}

function faktorisierung($n) {
testdivision($_POST['n']);
if ($erfolg==0){
for($k=1 ; $k<=ceil($_POST['n']^(1/3)); $k++){
for ($a=2*sqrt($k*$_POST['n']); $a<=floor(2*sqrt($k*$_POST['n'])+$_POST['n']^(1/6)/(4*sqrt($k))); $a++){
if(is_int(sqrt(a^2-4*$k*$_POST['n']))) {
echo "Faktor ist: " . ggt($a+sqrt(a^2-4*$k*$_POST['n']),$_POST['n']);
}
}
}
}
}


function testdivision($n){
$erfolg=1;
for ($i=2; $i<$_POST['n']^(1/3);$i++) {
if ($_POST['n'] % $i == 0) {
echo $_POST['n'] . "hat nichttrivialen Teiler" . $i ."<br>";
}
else {
$erfolg=0;
return $erfolg;
}
}
}

function ggt($a,$b){
if ($a > $b) {
$dummy=0;
$dummy=$a;
$a=0;
$a=$b;
$b=0;
$b=$dummy;
}
$c=1;
while ($c!=0) {
$c = $a % $b;
$a = $b;
$b=$c;
}
return $a;
}
?>

[undefined]

Habe jetzt nur drüber geflogen aber ein denkfehler bei deinem Script ist, das du $_POST Variablen als Integer behandelst - das sind sie nicht. Du solltest entweder Casten oder eine Strikte Typen Zuweisung verwenden.

rechne( (int)$_POST['n']);

[BLUESCREEN3D]

Wenn du schon eine Implementierung von einem Algorithmus postest, dann verlinke auch den Algorithmus:
http://de.wikipedia.org/wiki/Faktorisierungsmethode_von_Fermat#Faktorisierungsm ethode_von_Fermat_als_Primzahltest
http://de.wikipedia.org/wiki/Faktorisierungsmethode_von_Lehman

Zu Fermat:

1. Die for-Schleife erreicht nicht immer den Fall ($n+9)/6, z.B. wenn $n=1. Nur durch Ändern der Schleife kannst du das auch nicht korrigieren, sondern da musst du noch etwas programmieren, damit der Wert garantiert beachtet wird.
2. sqrt() gibt float zurück. is_int(sqrt()) wird also nie erfüllt sein. Ersetzte das is_int() also z.B. durch diese Funktion:

function float_is_integer($a)
{
return (fmod($a, 1) == 0.0);
}
3. Die Funktion rechne() hat den Parameter $n, arbeitet aber mit $_POST['n'].
4. Dein Quellcode könnte lesbarer sein: Du könntest z.B. eine Funktion is_square_number() einführen, um die if-Abfrage verständlicher zu machen.

Zu Lehmann:

Da sind ähnliche Fehler drin - korrigier die erstmal.
Außerdem steht in PHP der Operator ^ nicht für Potenzierung, sondern für XOR. Benutz die Funktion pow().