Ist es möglich in Java Primzahlen inkrementieren?

...komplette Frage anzeigen

6 Antworten

Natürlich, Du kannst jede Zahl inkrementieren (eins addieren), also auch eine Primzahl.

Was Du vermutlich meinst ist: Die nächste Primzahl zu finden. Das geht leider nicht so einfach. Du musst hierfür eine Zahl nach der anderen einem Primzahltest unterziehen, z. B. per Probedivision durch alle Zahlen bis zur Wurzel der zu untersuchenden Zahl oder, wenn Dich ein gewisser Fehler nicht stört, mit einem statistischen Primzahltest, wie dem Miller-Rabin-Verfahren. Das machst Du, bis Du die nächste Primzahl gefunden hast.

Es sollte eigentlich logisch sein, dass diese Funktionalität nicht bereits in die Sprache eingebaut ist. Du hast ein spezielles Problem, also musst Du passende Algorithmen implementieren (oder zumindest verwenden (*)), um es zu lösen.

(*) Miller-Rabin sollte bereits in der Klasse java.math.BigInteger implementiert sein. Falls Dich also die konkrete Umsetzung "nicht interessiert", kannst Du diese Implementierung einfach verwenden. Die Methode heißt isProbablePrime(...). Wenn Du tatsächlich etwas dabei lernen möchtest, solltest Du den Primzahltest - entweder per Probedivision oder per Miller-Rabin - natürlich selbst implementieren.

Schön ausführliche Antwort! Hast du aber nicht einen Fehler gemacht? 

"per Probedivision durch alle Zahlen bis zur Wurzel der zu untersuchenden Zahl"

Beispiel 16: Wurzel ist 4. 16 kann aber immer noch durch 8 geteilt werden.

Oder hast du das anders gemeint?

MfG

1
@Dultus

Beispiel 16: Wurzel ist 4. 16 kann aber immer noch durch 8 geteilt werden.

Das ist aber egal, da sie bereits durch 2 und 4 geteilt werden kann.

Es reicht, bis zur Wurzel zu suchen, da eine zusammengesetzte Zahl n ja als Produkt n = p * q geschrieben werden kann und dann mindestens einer der Faktoren kleiner gleich sqrt(n) sein muss.

Wenn n eine Quadratzahl ist, dann sind die Faktoren p und q gleich.

n = p * q = sqrt(n) * sqrt(n)

Wenn n keine Quadratzahl, aber zusammengesetzt ist, wird einer der Faktoren kleiner und einer der Faktoren größer sein.

Wenn n zusammengesetzt ist, ist sie also auf jeden Fall durch eine Zahl kleiner gleich sqrt(n) teilbar.

2

Dein Beispiel würde eine Endlossschleife produzieren (da m nie verändert wird und daher immer >0 ist). Aber davon abgesehen ist es auch ein mathematisch recht komplexes Thema, zu ermitteln, welches denn nun die nächste Primzahl ist. Ein Algorithmus, der relativ einfach zu verstehen, zu optimieren und auch performant ist (wenn du mal wissen willst, welche Primzahlen im Bereich > 1000000 sind), ist das Sieb des Erastothenes

https://www-i1.informatik.rwth-aachen.de/~algorithmus/algo25.php

https://de.wikipedia.org/wiki/Sieb_des_Eratosthenes

Von daher sieht der Code so aus

while(m>0){
System.out.println(n);
n+=this.getNextPrime();
}

und die Funktion "this.getNextPrime()" musst du dann logischerweise auch noch schreiben. Was da drin steht, ist unterschiedlich (könnte ein Eratosthenes-Sieb sein), viele Wege führen nach Rom. :)

n+=this.getNextPrime();

... wohl eher so ...

n = this.getNextPrime(n);

Erstens muss getNextPrime(...) ja wissen, ausgehend von welcher ("derzeitigen") Primzahl die "nächste" gesucht werden soll.

Zweitens möchte er ja (zumindest verstehe ich das so) die nächste Primzahl ausgeben (und nicht etwa alle Primzahlen addieren), also kein +=.

1

Wollte meinen Fehler im Code eh ausbessern, GuteFrage hat mich aber nicht gelassen :)

1

Hey ho,

Primzahlen werden sogar zu großen Preisen im Internet verkauft.

Erstmal kannst du bei 1 anfangen und +2 rechnen, da jede zweite Zahl sowieso keine Primzahl sein kann, da sie schließlich durch 2 teilbar ist.

Dann musst du eine Zahl solange mit n+1 teilen, bis die Hälfte der Primzahl erreicht wurde (wenn die Zahl größer als die Hälfte ist, kann man sowieso nicht mehr durch diese teilen).

Es darf kein Rest herauskommen. Könntest also mit Modulo rechnen. Dass Modulo nicht 0 sein darf. Sobald eine Zahl Modulo 0 ist, kann diese geteilt werden.

Rein von der Logik her wäre es so machbar (von Funktionen abgesehen).

MfG

Dann musst du eine Zahl solange mit n+1 teilen

Du meinst vermutlich, er muss sie durch alle Zahlen {2, 3, ..., n} bis zu einer gewissen Grenze n teilen.

bis die Hälfte der Primzahl erreicht wurde

Die (abgerundete) Wurzel reicht auch für die Obergrenze.

3
@NoHumanBeing

Ich meinte n als Zähler. Jedes mal n=n+1. Also z.B. 13. Hälfte 6,5 Also 2, 3, 4, 5, 6 - Schluss. Das kann man auch mit dem Modulo machen.

1

Du suchst vermutlich immer die nächste Primzahl. Da Du nicht der erste bist, gibt es dafür eine hoch optimierte Funktion: siehe

https://www.tutorialspoint.com/java/math/biginteger_nextprobableprime.htm

Sie ist sehr schnell, da nur zu 99,9999999...% sicher.

In den letzten 5 Jahren hat die komplette Internetgemeinde bis zu 5000 stellige Zahlen keinen einzigen Fehler gefunden! Erst ab 6000 stellige Zahlen sollte man die Funktion mit Vorsicht benutzen.

Nein, ist ja auch nicht sinnvoll.

Du kannst dir aber z.B. ne Methode "int nextPrime(int currPrime)" schreiben, die die nächste Primzahl nach currPrime ausgibt.

Bestens nimmst du eine Liste, die die Primzahlen bis eine Nummer enthält. Dann kannst du das Index inkrementieren, und die Zahl aus die Liste lesen.

Was möchtest Du wissen?