Primzahlen bis ins Unendliche

[Amateurprofi]

Und pünktlich zur Diskussion wurde eine neue mersennesche Primzahl gefunden.....

Zitat:

On December 15, 2005, Dr. Curtis Cooper and Dr. Steven Boone, professors at Central Missouri State University, discovered the 43rd Mersenne Prime, 230,402,457-1. The CMSU team is the largest contributor to the GIMPS project.

The new prime is 9,152,052 digits long. This means the Electronic Frontier Foundation $100,000 award for the discovery of the first 10 million digit prime is still up for grabs! The new prime was independently verified in 5 days by Tony Reix of Bull S.A. in Grenoble, France using 16 Itanium2 1.5 GHz CPUs of a Bull NovaScale 6160 HPC at Bull Grenoble Research Center, running the Glucas program by Guillermo Ballester Valor of Granada, Spain.

http://www.mersenne.org/

[Sascha_OW]

ich habe jetzt folgendes Programmiert:

Delphi-Quellcode:

function ist_prim (zahl: longint): boolean;
var  teilbar : boolean;
     i       : longint;
     str     : string;
     str_    : string;
     str_3  :  string;
begin
  str := '';
  str_ := '';
  str_3 := '';
  teilbar := true;
  i := 2;
      While i <= sqrt(zahl)  do begin
      str := Inttostr(i);
      If length(Str) >2 then begin
        str_ := str[length(str)];
        str_3 := str[length(str) - 2] + str[length(str) - 1] + str[length(str)];
        If (str_ = '2') and (str_ = '4') and (str_ = '6')and (str_ = '8') and (str_ = '0') then result := false;
        If (Strtoint(str_3) mod 8 = 0) then result := false;
        If Quersumme(i) mod 3 = 0 then result := false;
        if Quersumme(i) mod 9 = 0 then result := false;

      end;
          If (Zahl mod i=0)  and (i<>zahl) then begin
             teilbar := false;
          end;
          inc(i);
      end;
  result := teilbar;
end;

und zum aufrufen:

Delphi-Quellcode:

 For i := 1 to Strtoint(Edit1.Text) do begin
 If ist_prim(i) then begin
   Form1.caption := inttostr(i);
   Memo1.Lines.add (Inttostr(i));
 end;
 Form1.Refresh;
 end;

jetzt ist die frage, wie bekomme ich das hin das ich das bis ins unendliche mache und wie mach ich das schneller?=

[Achim Kalwa]

Hallo Sascha,

Zitat:

jetzt ist die frage, wie bekomme ich das hin das ich das bis ins unendliche mache und wie mach ich das schneller?=

ein paar Anmerkungen zu Deinem Code:

Deine Schleife fängt bei 1 an und zählt in Einer-Schritten weiter. D.h. jede zweite Zahl, welche Du testest, ist sowieso schon nicht prim, weil Sie durch 2 teilbar ist. Die erste Optimierung wäre also, die geraden Zahlen zu überspringen. Beginne mit 3 und zähle in Zweierschritten weiter Inc(i, 2);

Du verwendest als Variablen-Bezeichner Str, Str_ und Str3. Der Name "Str" ist schon durch eine Delphi-eigene Funktion belegt, das verwirrt hier nur. Denke Dir eigene Namen für Deine Variablen aus. Beim schnellen überfliegen Deines Codes habe ich auch Str und Str_ nicht auseinander halten können. Wähle sinnvolle Bezeichner ("Ziffer").

String-Operationen sind sehr langsam im Vergleich zu numerischen Operationen. Du wandelst die Zahl in einen String, um dann an die einzelnen Ziffern zu gelangen. Das kostet extrem viel Rechenzeit.

Da Du ohnehin nur die einzelnen Ziffern zwischenspeicherst, ist String auch der ungeeignete Datentyp. "Char" reicht dafür aus, belegt nur ein Byte und kommt ohne den ganzen Overhead aus, der Strings so bequem macht.

Deine "Zahl" ist vom Typ "Longint"; die größte Zahl, die Du damit verarbeiten kannst, ist 2^31 = 2.147.483.647, also eine Zahl mit 10 Stellen. Zum Vergleich: Die jüngst gefundene Primzahl M43 hat über 9 Millionen Stellen!

Dein "Hauptfenster" führt bei jeder Zahl ein Refresh durch; auch das kostet viel Zeit. Zähle mit, wieviele Zahlen du geprüft hast und mach ein Refresh z.B. nur nach jeweils 100 geprüften Zahlen. Oder nur dann, wenn Du eine Zahl als prim identifiziert hast.

Wenn Du Dir also die 100.000 US-Dollar Preisgeld einsacken willst, musst Du Deinen Code noch etwas umschreiben :zwinker:

Achim

[icqgoofy]

Hallo erstmal,

also ein für allemal:

Es gibt KEINE höchste Primzahl!
Der Beweis ist ganz einfach:

Die höchste Primzahl nennen wir:

Code:

Pmax

Man reihe die Menge aller Primzahlen nacheinander auf:

Code:

2, 3, 5, 7, .............. bis Pmax

Nun multiplizieren wir all diese Zahlen:

Code:

2*3*5*7*.....*Pmax

und erhalten eine Zahl,die wir PM nennen und die durch alle Primzahlen zu teilen ist
(Primfaktorzerlegung)
also:

Code:

2*3*5*7*.....*Pmax = PM

Nun addieren wir zu dieser Zahl PM die Zahl 1, aso:

Code:

PM + 1

und diese neue gewonnene Zahl ist erneut eine Primzahl, da sie durch
keine Zahl zu teilen ist!!!!
Da man Pmax beliebig definieren kann gibt es folglich
KEINE höchste Primzahl.

Gruß icqgoofy

[glkgereon]

Dein Beweis hinkt an einer Stelle:

Warum ist PM + 1 eine Primzahl?

Ist für mich nicht ersichtlich...

[icqgoofy]

Hi,

"Ganz einfach",
weil jene Zahl, weder durch 2, 3, 5, 7, ....... noch Pmax teilbar ist,
da ja die VORGÄNGERZAHL durch all diese Zahlen teilbar ist.
Und da es auf Grund der Primfaktorzerlegung KEINE
anderen Zahlen geben kann, durhc die jene Zahl teilbar ist,
da, wie der Name schon sagt, die Primfaktorzerlegung
eine Zahl in alle in ihr befindlichen Primzahlen zerlegt,
und da ALLE Primzahlen in der VORGÄNGERZAHL enthalten sind,
MUSS diese Zahl eine Primzahl sein.

Gruß icqgoofy

[glkgereon]

Zitat:

Zitat von icqgoofy

Hi,

"Ganz einfach",
weil jene Zahl, weder durch 2, 3, 5, 7, ....... noch Pmax teilbar ist,
da ja die VORGÄNGERZAHL durch all diese Zahlen teilbar ist.
Und da es auf Grund der Primfaktorzerlegung KEINE
anderen Zahlen geben kann, durhc die jene Zahl teilbar ist,
da, wie der Name schon sagt, die Primfaktorzerlegung
eine Zahl in alle in ihr befindlichen Primzahlen zerlegt,
und da ALLE Primzahlen in der VORGÄNGERZAHL enthalten sind,
MUSS diese Zahl eine Primzahl sein.

Gruß icqgoofy

ok, ich nehme meinen einwand zurück....das überzeugt :)

[icqgoofy]

Gut:)
Wow, ich glaube das war der ERSTE Beitrag den ich in diesem
Forum beantwortet hab:D
Bin sonst ein reiner Fragensteller.
(bin jo ach noch net lange dabei)

Gruß icqgoofy

[Airblader]

Wurde das nun nicht schon 3-4 Mal erklärt? ;)

Hier gehts inzwischen auch mehr um das Ermitteln einer hoheh Primzahl, nicht die höchste :)

air

[glkgereon]

Zitat:

Zitat von Airblader

Wurde das nun nicht schon 3-4 Mal erklärt? ;)

Hier gehts inzwischen auch mehr um das Ermitteln einer hoheh Primzahl, nicht die höchste :)

air

dieses Verfahren ermöglichst dies aber doch...

In Kombination mit der DEC ist es doch super-einfach...oder seh ich da was falsch?

PseudoCode:

Delphi-Quellcode:

While not Abgebrochen do
  begin
  AktPrime:=(AktPrime-1)*AktPrime+1;
  Output(AktPrime);
  end;

Überlegung:
Eine neue Primzahl kann man berechnen aus der letzten primzahl multipliziert mit derm Produkt aller Primzahlen davor...
Gleichzeitig ist aber das Produkt aller davor gleich der aktuellen primzahl-1
somit sei die neue primzahl die alte mal die alte minus eins.

mit dem Startwert 2 gäbe das:
(2-1)*2+1 = 3
(3-1)*3+1 = 7
(7-1)*7+1 = 43

sind zwar längst nicht alle (da fehlen aber sehr viele :shock: ) aber es sind offensichtlich primzahlen....