Weitere Nachkommastellen bei Berechnung nutzen

[GrafZhL]

Hallo, bin ganz neu hier, zumindest im Forum :)

Es geht um ein Skript, das eine Zahl darauf überprüft, ob es eine Primzahl ist.

Bislang sieht das bei mir so aus (nachdem man auf index.php im Formular die zu überprüfende Zahl eingegeben hat):

  
<?php  
$zahl = $_REQUEST['zahl'];  
if($zahl == "") {  
print "Bitte eine Eingabe machen!";  
}  
elseif($zahl < 2) {  
print "Nur Zahlen ab 2 eingeben!";  
}  
  
$count = 2;  
  
while($count <= $zahl) {  
  
$division = $zahl/$count;  
$division2 = $division/2;  
$division2round = round($division2);  
  
if($division == 1) {  
print "Die Zahl $zahl ist eine Primzahl!";  
break;  
}  
elseif($division2round == $division2) {  
print "Die Zahl $zahl ist keine Primzahl. Sie ist zum Beispiel durch $count teilbar.";  
break;  
}  
$count++;  
}  
?>  

Unabhängig davon prüft die if-Abfrage, ob $division == 1 und damit $zahl == $count ist. Hier liegt glaube ich auch der Ursprung meines Problems, zu dem ich noch komme. Falls $zahl == $count, bricht die while Schleife, die vorher eingesetzt hat und läuft, bis $count == $zahl ist, ab und man erhält die Nachricht, dass die eingangs gewählte Zahl eine Primzahl ist; $count erhöht sich natürlich bei jedem Durchlauf um 1.

Falls $count noch nicht $zahl ist, wird überprüft, ob $zahl glatt durch $count, das mit dem Wert 2 beginnt, teilbar ist (etwas umständlich, das gebe ich zu, bin aber PHP Neuling und das ist bis jetzt die einzige Methode, die mir dazu einfiel). Ist es der Fall, so ist $zahl logischerweise keine Primzahl, da sie durch eine Zahl != $zahl teilbar ist.

Nun zu meinem Problem. Gibt (relativ) große Zahlen ein, so hat diese Methode der Überprüfung den Nachteil, dass es sehr abhängig von den Nachkommastellen von $division ist. So behauptet das Skript beispielsweise, 99997 sei eine Primzahl, obwohl es keine ist (19 * 19 * 277). Teilt man also z.B. 99997 durch 99996 (wenn $count == 99996), dann ist für PHP $division == 1 und 99997 damit eine Primzahl.

Wie kann mal also mehr Nachkommastellen in die Berechnung mit einbeziehen, sodass man (zumindest im Rahmen bis 1000000) sicher Primzahlen festellen kann?

[GrafZhL]

Ähm. Das Skript hat offenbar noch ganz andere Probleme. Angeblich ist auch 15 eine Primzahl... Da muss ich wohl sowieso nochmal drüber schauen x_x

[Tom]

Hello,

Ähm. Das Skript hat offenbar noch ganz andere Probleme. Angeblich ist auch 15 eine Primzahl... Da muss ich wohl sowieso nochmal drüber schauen x_x

Vielleicht schaust Du da dann doch nochmal im Web unter "Sieb des Eratosthenes"
http://de.wikipedia.org/wiki/Sieb_des_Eratosthenes

Wie groß sollen denn die Zahlen werden, die Du auf Primzahl prüfen willst?

Liebe Grüße aus Syburg bei Dortmund

Tom vom Berg

[GrafZhL]

Öhöm, hier die geupdatete Version...

  
<?php  
$zahl = $_REQUEST['zahl'];  
if($zahl == "") {  
print "Bitte eine Eingabe machen!";  
}  
elseif($zahl < 2) {  
print "Nur Zahlen ab 2 eingeben!";  
}  
  
$count = 2;  
  
while($count <= $zahl) {  
  
$division = $zahl/$count;  
$divisionround = round($division);  
  
if($division == 1) {  
print "Die Zahl $zahl ist eine Primzahl!";  
break;  
}  
elseif($divisionround == $division) {  
print "Die Zahl $zahl ist keine Primzahl. Sie ist zum Beispiel durch $count teilbar.";  
break;  
}  
$count++;  
}  
?>  

Jetzt funktioniert es doch. Nur das Zeitlimit wird bei sehr großen Zahlen überschritten (also die 60 Sekunden).

Entschuldigung für meinen vorschnellen Schrei nach Hilfe!

[Tom]

Hello,

Jetzt funktioniert es doch. Nur das Zeitlimit wird bei sehr großen Zahlen überschritten (also die 60 Sekunden).

Was sind denn "sehr große Zahlen" für Dich?

Größer als int?

Liebe Grüße aus Syburg bei Dortmund

Tom vom Berg

[GrafZhL]

int? :D

Eine große Zahl, bei der anscheinend viel zu berechnen ist, ist für mich z.B. 88889887. Im Vergleich zu größeren Zahlen ist das natürlich eine kleinere Zahl (oh wie war das sinnig). Aber meinem Skript macht sie anscheinend Probleme.

Was sind denn "sehr große Zahlen" für Dich?

Größer als int?

[MudGuard]

Hi,

Optimierungen:

while($count <= $zahl) {

Wenn es Teiler außer 1 und der Zahl selbst gibt, ist einer kleiner oder gleich der Wurzel der Zahl, der andere größer oder gleich der Wurzel.
Es ist also nicht notwendig, den Zähler bis zur Zahl selbst laufen zu lassen, man kann bereits abbrechen, wenn die Wurzel der Zahl überschritten wurde.
Dann ist die Zahl eine Primzahl.

Das spart schon mal einen Haufen Laufzeit ein.

$count++;

Ich würde den Teiler 2 extra behandeln.
Wenn dies nicht zum Ergebnis keine Primzahl führt (sprich: die $zahl ist ungerade), dann braucht man nicht mehr durch gerade Zahlen zu teilen versuchen, denn wenn es einen geraden Teiler gäbe, wäre auch die 2 Teiler.

Es reicht also, mit 2 und dann mit 3, 5, 7, 9, 11, ... zu testen.

Das sorgt in etwa für die Halbierung der Laufzeit.

Und statt
$division = $zahl/$count;
$divisionround = round($division);
würde ich eher
$rest = $zahl % $count;
benutzen und prüfen, ob der Rest 0 ist (==> keine Primzahl)

Weitere Optimierungen wären möglich ...

cu,
Andreas

[Vinzenz Mai]

Hallo

Hallo, bin ganz neu hier, zumindest im Forum :)

Du bist willkommen.

Es geht um ein Skript, das eine Zahl darauf überprüft, ob es eine Primzahl ist.

Du solltest auf Tom hören :-)

<?php
$zahl = $_REQUEST['zahl'];
if($zahl == "") {
    print "Bitte eine Eingabe machen!";
}
elseif($zahl < 2) {
    print "Nur Zahlen ab 2 eingeben!";
}

// Jede Zahl ist durch 1 teilbar :-)
// Teile durch Zahlen von 2

$count = 2;

// bis zur Zahl selbst

while($count <= $zahl) {

// Eine einleuchtende Optimierung:
// Du kannst bei der kleinsten ganzen Zahl aufhören, die größer ist
// als die Wurzel der Zahl, sonst hättest Du den kleineren Faktor bereits
// finden müssen.

$division = $zahl/$count;

// Du arbeitest mit ganzen Zahlen, bringst hier aber mit der Division
// Gleitpunktzahlen hinein

// Schau' Dir doch den Rest bei der Division an, d.h. benutze den
// [link:http://www.php.net/manual/de/language.operators.arithmetic.php@title=Modulo-Operator] und erspare Dir so die Ungenauigkeiten.

[...]

// War der Rest 0, dann gibt es einen Teiler -> und Du kannst aufhören
// Markiere, dass Du etwas gefunden hast (vor der Schleife bitte mit false
// initialisieren.
//         $found = true;

print "Die Zahl $zahl ist keine Primzahl. Sie ist zum Beispiel durch $count teilbar.";

break;
      }
      $count++;
  }

[...]
// Bist Du bis zur oberen Schranke gekommen (und
// $found ist immer noch false, dann

print "Die Zahl $zahl ist eine Primzahl!";

}
?>

  
Somit sparst Du Dir einige teure Divisionsoperationen je Schleifendurchlauf,  
der Timeout wird somit später erreicht und ...  
  

> Wie kann mal also mehr Nachkommastellen in die Berechnung mit einbeziehen, sodass man (zumindest im Rahmen bis 1000000) sicher Primzahlen festellen kann?  
  
... Nachkommastellen spielen keine Rolle mehr und können daher kein Problem mehr hervorrufen. Aber ich wiederhole nochmals:  
  
Du solltest auf [Tom](https://forum.selfhtml.org/?t=175674&m=1154859) hören und Dir das Sieb des Eratosthenes anschauen.  
  
Denke bitte daran, dass Du recht schnell die Grenzen der Integerzahlen erreichen kannst. Spätestens dann solltest Du zu den [Zahlen mit beliebiger Genauigkeit](http://www.php.net/manual/de/book.bc.php) übergehen. Sicherlich aus diesem Grund hat Tom [Dich gefragt](https://forum.selfhtml.org/?t=175674&m=1154864), was Du unter großen Zahlen verstehst.  
  
  
Freundliche Grüße  
  
Vinzenz

[Tom]

Hello,

Du solltest auf Tom hören und Dir das Sieb des Eratosthenes anschauen.

Denke bitte daran, dass Du recht schnell die Grenzen der Integerzahlen erreichen kannst. Spätestens dann solltest Du zu den Zahlen mit beliebiger Genauigkeit übergehen. Sicherlich aus diesem Grund hat Tom Dich gefragt, was Du unter großen Zahlen verstehst.

So war das gedacht.
Es gibt auch andere Ansätze.
http://www.mathe.tu-freiberg.de/~hebisch/cafe/primzahlen.html
http://de.wikipedia.org/wiki/Mersenne-Primzahl

und die "größte bekannte Primzahl" 2^(30402457)-1 ist ja auch nicht ohne.

Was mich immer interessiert hat dabei, ist das Muster das entsteht (die Primzahldichte) und die Anzahl der bisher gefundenen. Gibt es darüber verbindliche Aussagen? Ich habe bisher keine gefunden.

Liebe Grüße aus Syburg bei Dortmund

Tom vom Berg

[Jens Holzkämper]

Tach,

Was mich immer interessiert hat dabei, ist das Muster das entsteht (die Primzahldichte)

die Dichte läßt sich ziemlich exakt abschätzen (zumindestens für große Mengen von Primzahlen): Die Anzahl der Primzahlen kleiner als x ist etwa [latex]
\frac{x}{\ln(x)}
[/latex], die Abstände zwischen zwei Primzahlen werden dabei übrigens beliebig groß (http://de.wikipedia.org/wiki/Primzahllücke), ob es auch beliebig viele Primzahlzwillinge gibt, ist dagegen noch nicht bewiesen aber zumindestens ist es die übliche Annahme.

und die Anzahl der bisher gefundenen.

Es sind endlich viele bekannt.

mfg
Woodfighter

[Jens Holzkämper]

Tach,

verdammt, zu früh abgeschickt:

und die Anzahl der bisher gefundenen.

Es sind endlich viele bekannt.

, wären es mehr, gäbe es nämlich keine größte bekannte Primzahl mehr ;-)

mfg
Woodfighter

[Tom]

Hello Jens,

und die Anzahl der bisher gefundenen.

Es sind endlich viele bekannt.

, wären es mehr, gäbe es nämlich keine größte bekannte Primzahl mehr ;-)

jetzt weiß ich nicht, ob ixh lachen oder weinen soll.
Ich wollte doch wissen, wieviele den "endlich viele" inzwischen bedeutet, aber das weißt Du sicher auch. Ich habe allerdings keine Information darüber gefunden.

Außerdem nehme ich an, dass die "größte bekannte Primzahl" keinesfalls mit dem (sicheren) Sieb des Eratosthenes, sondern eben mit der "Mersenneschen Methode" gefunden worden ist. Daher nehme ich an, dass es zwischen der "größten bekannten Primzahl" und den nach klassischer Methode gefundenen noch etliche Lücken gibt. Oder habe ich da was vollkommen verkehrt verstanden?

Liebe Grüße aus Syburg bei Dortmund

Tom vom Berg

[Jens Holzkämper]

Tach,

Ich wollte doch wissen, wieviele den "endlich viele" inzwischen bedeutet, aber das weißt Du sicher auch. Ich habe allerdings keine Information darüber gefunden.

ich denke, diese Information ist unbekannt. Es gibt einfach kein Interesse an einer Liste aller dem Autor bekannter Primzahlen, sie wäre eh nie vollständig. Und da es ja eine gute zahlentheoretische Methode zur Abschätzung der Menge gibt, wird sich niemand den Aufwand machen.

Außerdem nehme ich an, dass die "größte bekannte Primzahl" keinesfalls mit dem (sicheren) Sieb des Eratosthenes, sondern eben mit der "Mersenneschen Methode" gefunden worden ist.

Ja, Mersenne-Zahlen sind dank Lucas Lehmer erheblich leichter auf Primalität zu testen.

Daher nehme ich an, dass es zwischen der "größten bekannten Primzahl" und den nach klassischer Methode gefundenen noch etliche Lücken gibt.

Korrekt, du kannst also annehmen, dass
[latex]
\frac{2^{32582657}}{\ln(2^{32582657})} \approx 5,515933592 * 10^{9808349}
[/latex]
eine gute obere Grenze für die Anzahl an momentan bekannten Primzahlen ist.

mfg
Woodfighter

[Tom]

Hello,

Daher nehme ich an, dass es zwischen der "größten bekannten Primzahl" und den nach klassischer Methode gefundenen noch etliche Lücken gibt.

Korrekt, du kannst also annehmen, dass
[latex]
\frac{2^{32582657}}{\ln(2^{32582657})} \approx 5,515933592 * 10^{9808349}
[/latex]
eine gute obere Grenze für die Anzahl an momentan bekannten Primzahlen ist.

*ups*
Die passen wohl doch nicht alle auf meine neue Festplatte :-(

Liebe Grüße heute aus Braunschweig

Tom vom Berg