Primzahlen bis ins Unendliche

[GuenterS]

Zitat:

Zitat von 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....

Und das machst Du bis du eine Primzahl hast, welche aus 10 Millionen Stellen besteht.

[glkgereon]

Zitat:

Zitat von GuenterS

Und das machst Du bis du eine Primzahl hast, welche aus 10 Millionen Stellen besteht.

Joa...wieso nicht?^^

Da sich die anzahl der Stellen immer verdoppelt (gaaanz grob...) wären das dann Wurzel(10Mio) Schritte...etwa 3200

[negaH]

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

Ah, interessante These ;)

2*3*5*7*11*13 = 30030

30031 müsste demnach eine Primzahl sein, richtig ?

30031 = 59 * 509

Zitat:

Zitat von Günter S

Ü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

Aha ebenfalls eine interessante These:

(43-1) * 43 +1 = 1807

1807 müsste demnach eine Primzahl sein, richtig ?

1807 = 13 * 139.

Shit wenn die Zahlen doch nicht so widerspenstig wären ;)

Aber woran scheiterts ??

Zitat:

Zitat von Euklid

Widerspruchsbeweis: Nimmt man an, daß es nur endlich viele Primzahlen gibt, also etwa p1, p2, ... pn, dann ist die Zahl m=p1*p2* ... *pn+1 größer als alle diese Primzahlen und wird von keiner Primzahl geteilt. Also ist m selbst eine Primzahl, ein Widerspruch zur Annahme.

Damit kann man beweisen das es unendlich viele Primzahlen gibt, weil die Annahme "endlich viele" eben FALSCH ist. Dieser Beweis kann nicht dazu dienen eine Konstruktionsregel für Primzahlen zu bauen, da er eben beweist das es nicht endlich viele Primzahlen gibt. Die Konstruktionsregel kann nur dann funktionieren wenn es endlich viele Primzahlen gäbe, da dies aber nicht der Fall ist widerspricht sich die gewählte Konstruktionsregel selber ;)

Dh. Wenn wir annehmen das es nur endlich viele Primzahlen gäbe dann müsste das Produkt aus allen vorherigen Primzahlen +1 (unsere Konstruktionsregel) ebenfalls eine neue Primzahl sein da sie nicht durch ihre Vorgänger teilbar ist. Da damit aber implizit widerlegt wurde das es nur endlich viele Primzahlen gibt muß unsere Konstruktonsregel zur Berechnung einer neuen Primzahl ebenfalls falsch sein.

Der wörtlich korregierte Beweis des Euklids müsste nämlich so lauten:

Zitat:

Zitat von Euklid

Bildet man das Produkt aus allen Primzahlen und addiert +1 dann kann keiner der verwendeten Faktoren ein Teiler der so entstandenen Zahl sein, denn stets bleibt beim Teilen der Rest 1. Das bedeutet diese Zahl muß eine bislang unbekannte Primzahl als Teiler besitzen die größer als die größte bekannte Primzahl ist und demzufolge muß es unendlich viele Primzahlen geben.

Gruß Hagen

[markusj]

Man müsste einen anderen Algorithmus finden, dessen Rechenaufwand linear zu der Anzahl der Stellen ansteigt, anstatt Quadratisch.
Mir ist es vor kurzem gelungen, den Aufwand für die Kontrolle einer ListBox/StringList nach doppelten Einträgen zu linearisieren^^. Das ging aber nur, weil die Daten über ein 4D-Array zu repräsentieren waren --> 4D-Array od Boolean gemacht und beim zweiten mal Zugreifen auf einen Wert wird der ListBox-Eintrag rausgeworfen.
Das Problem ist hier, dass man bei einem solchen Sieb einen extremen Aufwand hätte ...und der RAM-Verbrauch eines Arrays[2..10^10] ist ja auch nicht ganz gering

mfG

Markus

[alzaimar]

Zitat:

Zitat von markusj

Mir ist es vor kurzem gelungen, den Aufwand für die Kontrolle einer ListBox/StringList nach doppelten Einträgen zu linearisieren^^.

Versuchs mal mit einer Hashmap, dann wird das nicht linearisiert, sondern bleibt bei O(1) (was Du vielleicht meintest). Bringt aber auch nichts. Imho bleibt die einzig sinnvolle Möglichkeit immer noch die, nach aussichtsreichen Kandidaten zu suchen (mit den einschlägig bekannten Verfahren) und die eben nach guter alter Brute-force Art zu überprüfen.

[Jasocul]

[quote="Luckie"]

Zitat:

Zitat von glkgereon

Nach unserem Wissen gibt keine höchste Primzahl.

Das würde ich nicht so laut sagen, denn wie du selbst sagst:

Zitat:

Wenn die Folge der Primzahlen irgendwann aufhören sollte (also es eine höchste gibt) so musst du mir das erstmal beweisen ;)
Und genau das ist eben bisher weder bewiesen, noch widerlegt worden.

Doch.
Annahme: N ist höchste Primzahl.
Man multipliziere alle Primzahlen bis N miteinander.
Dann addiere man 1.
Diese Zahl ist nicht durch die bisherigen Primzahlen teilbar!
Folglich ist sie selbst eine Primzahl oder es gibt andere Primzahlen außer den bisher bekannten.

Beweis durch Widerspruch. Mathe Grundstudium.

[markusj]

@alzaimar

Ne, so hab ichs nicht gemeint

In meiner ListBox sind durch den User bearbeitbare Koordinaten, die übersetze ich in mein Array, ist dort bereits eintrag vorhanden, habe ich eine Doublette und lösche sie. Die Information selbst bleibt in meiner Listbox gespeichert, ich verwende das Array nur zur Kontrolle auf Zwillinge.

mfG

Markus

PS: was meinst du mit O(1)
@Peter
PPS: Shit Roter Kasten: Hagen hat zu dem neuen Post etwas weiter unten einen Interessanten Beweis geliefert, der so ähnlich ging wie deiner, aber Wiedersprach (zumndest der verwendeten Formel)

EDIT: Oder sie ist durch 2 teilbar? Moment ...
Primzahl != Ungerade Zahl ... Ungerade Zahl*Ungerade Zahl := Ungerade Zahl, oder???
+1 := gerade Zahl. Gerade Zahl div 2 != 0 ... Was jetzt?

@alzaimar
EDIT2: Der Übersicht halber sortier ich nochmal um ...

[alzaimar]

@markusj:Das wird jetzt aber konfus... (Wer antwortet wem etc...)... O(1) bedeutet, das der Aufwand unabhängig von der Anzahl ist. Hashmaps haben die Eigenschaft, das sie immer gleich schnell sind, egal ob in der Liste nun 10 oder 100.000.000 Einträge sind.

[Loki77]

:wink:

Zitat:

Zitat von gsh

Also Primzahlen sind zahlen die nur durch sich selber oder durch eins teilbar sind.

Zusatz: laut taschenbuch der Mathematik (Brostein,....)
...Und GENAU 2 Ergebnisse haben.
--was ist denn dann mit "1"???
Klugscheisser der ich nun mal bin...

[markusj]

Eins ist nicht Prim ... es gibt immer nur 1