Wie implementiere ich diese mathematische Erkenntnis?

... komplette Frage anzeigen

4 Antworten

Mikkey hat eigentlich schon alles gesagt. Aber ich sehe da noch ein paar Verständnisprobleme. Also da capo:

Deine Erkenntnis kann man so nutzen: Nicht-prime Teiler von z brauchst Du gar nicht erst probieren. Dumm nur, dass Du keine Liste aller Primzahlen hast (und falls doch, wäre Dein Algorithmus ja überflüssig).

Aber Du kannst es wenigstens für einige Primzahlen umsetzen:

  • Prüfe auf Teilbarkeit durch 2 und ignoriere alle Vielfachen davon als mögliche Teiler. Das geht sehr leicht und halbiert die Rechenzeit (50%).
  • Prüfe zusätzlich auf Teilbarkeit durch 3 und ignoriere danach auch alle Vielfachen von 3. Es bleiben nur noch potentielle Teiler der Form 6i+1 und 6i+5 übrig, wobei 6·0+1 ein Sonderfall ist. Den umgeht man leicht, indem man auf Teilbarkeit durch 6i+5 und 6i+7 testet. Damit schrumpft die Rechenzeit auf 1/3 (33%).
  • Um auch Vielfache von 5 zu ignorieren, baust Du eine Liste aller Zahlen zwischen 7 und 31 (=2·3·5+1), die nicht durch 2, 3 oder 5 teilbar sind. Getestet wird dann einmalig auf 2, 3 und 5, danach nur noch auf 30i+{7, 11, 13, 17, 19, 23, 29, 31}, also nur noch 8/30 aller Werte (27%).
  • Willst Du auch die 7 mitnehmen, brauchst Du alle Werte zwischen 9 und 211 (=2·3·5·7+1), die nicht durch 2, 3, 5 oder 7 teilbar sind. So prüfst Du nur noch 48 von 210 Werten (23%).

Während mit weiteren Primzahlen die Kandidatenliste schnell ansteigt, geht die Laufzeit dabei immer dürftiger zurück. Deshalb spart man sich meist den Aufwand und begnügt sich mit den 50% bei ungeraden Zahlen.


Ein ganz anderes Thema ist, nur nach Teilern bis √n zu suchen:

Stell Dir vor, Dein Algorithmus braucht zum Prüfen einer großen Primzahl einen ganzen Tag (24h). Mit dem Ungerade-Trick allein drückst Du das auf 12h, und durch Überspringen der 3er, 5er und 7er weiter auf 8h, 6,4h und 5,5h — naja...

Die Begrenzung der Teiler auf √n bringt Dich aber sofort auf 0,3 Sekunden Rechenzeit (bei 1µs/Test). Die obigen Verfahren sehen dagegen ziemlich alt aus!

Antwort bewerten Vielen Dank für Deine Bewertung

Vielen Dank euch beiden für eure sehr nützlichen Beiträge.

Hoffe ich habe das alles jetzt auch richtig implementiert, wobei ich dazu noch sagen muss das ich die vielfachen nur von 2 und 3 berücksichtigt habe.

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von ralphdieter
05.12.2015, 23:36

Tut das?

Ich denke, Du musst i*i<=n schreiben; sonst winkst Du die 25 als Primzahl durch. Aber die Zweierschritte sind jetzt auch falsch. Ich würde i ab 5 in Sechserschritten erhöhen und dabei die Teiler i und i+2 prüfen:

for ( int i=5; i*i<=n; i+=6 )

Außerdem fehlen in Deiner Prüfung Klammern (Punkt vor Strich):

  if ( n%i==0 || n%(i+2)==0 )

Sonst sieht alles gut aus. Zum Testen kannst Du ja alle Primzahlen bis 10000 ausgeben und das mit Deinem Original vergleichen.

1

So jetzt müsste alles Stimmen und vielen Dank nochmals :D

Antwort bewerten Vielen Dank für Deine Bewertung

Am Anfang solltest Du auf "< 2" prüfen, da Du sonst alle negativen Zahlen als Primzahlen ausweist.

Ferner kannst Du vorab auf die Teilbarkeit durch 2 prüfen und anschließend nur die Teilbarkeit durch ungerade Zahlen ab 3 prüfen.

Zu guter Letzt genügt es, Teiler zu suchen, die kleiner oder gleich der Wurzel von n sind (Bedingung i*i <= n)

Wenn Du eine Liste von Primzahlen hast, brauchst Du natürlich nur die Teilbarkeit durch diese zu überprüfen. So eine Liste steht aber im Allgemeinen nicht zur Verfügung. Ansonsten könntest Du auch einfach feststellen, ob n in dieser Liste enthalten ist.

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von seanjohn123
04.12.2015, 18:25
Passts so ? Ist dadurch auch die math. Kenntnis berücksichtigt ? 



public static boolean isPrime2(int n) { if(n < 2) { return false; } if(n % 2 == 0) { // wenn 2 eine Zahl nicht teilen kann, dann kann es auch keine andere gerade Zahl return false; } for (int i = 3; i * i < n; i++) { // bis zur Quadratwurzel zu prüfen, wenn bis dahin kein Teiler // gefunden ist, handelt es sich um eine Primzahl if (n % i == 0) return false; i++; // // nur durch ungerade Zahlen teilen } return true; }}
0

Was möchtest Du wissen?