Primzahlen in Java generieren

1. Einleitung

In diesem Tutorial zeigen wir verschiedene Möglichkeiten, wie wir mit Java Primzahlen generieren können.

Wenn Sie überprüfen möchten, ob eine Zahl eine Primzahl ist, finden Sie hier eine Kurzanleitung dazu.

2. Primzahlen

Beginnen wir mit der Kerndefinition. Eine Primzahl ist eine natürliche Zahl größer als eine, die keine positiven Teiler außer eins und sich selbst hat.

Zum Beispiel ist 7 eine Primzahl, weil 1 und 7 die einzigen positiven ganzzahligen Faktoren sind, während 12 nicht, weil es die Teiler 3 und 2 zusätzlich zu 1, 4 und 6 hat.

3. Generieren von Primzahlen

In diesem Abschnitt werden wir sehen, wie wir effizient Primzahlen generieren können, die unter einem bestimmten Wert liegen.

3.1. Java 7 und früher - Brute Force

public static List primeNumbersBruteForce(int n) { List primeNumbers = new LinkedList(); for (int i = 2; i <= n; i++) { if (isPrimeBruteForce(i)) { primeNumbers.add(i); } } return primeNumbers; } public static boolean isPrimeBruteForce(int number) { for (int i = 2; i < number; i++) { if (number % i == 0) { return false; } } return true; } 

Wie Sie sehen können, iteriert primeNumbersBruteForce über die Zahlen von 2 bis n und ruft einfach die Methode isPrimeBruteForce () auf, um zu überprüfen, ob eine Zahl eine Primzahl ist oder nicht.

Die Methode überprüft die Teilbarkeit jeder Zahl durch die Zahlen in einem Bereich von 2 bis Nummer 1 .

Wenn wir irgendwann auf eine teilbare Zahl stoßen, geben wir false zurück. Am Ende, wenn wir feststellen, dass diese Zahl durch keine ihrer vorherigen Zahlen teilbar ist, geben wir true zurück und geben an, dass es sich um eine Primzahl handelt.

3.2. Effizienz und Optimierung

Der vorherige Algorithmus ist nicht linear und hat die zeitliche Komplexität von O (n ^ 2). Der Algorithmus ist auch nicht effizient und es gibt eindeutig Raum für Verbesserungen.

Schauen wir uns die Bedingung in der Methode isPrimeBruteForce () an .

Wenn eine Zahl keine Primzahl ist, kann diese Zahl in zwei Faktoren zerlegt werden, nämlich a und b, dh Zahl = a * b. Wenn sowohl a und b waren größer als die Quadratwurzel von n , a * b wäre größer als n .

Mindestens einer dieser Faktoren muss also kleiner oder gleich der Quadratwurzel einer Zahl sein. Um zu überprüfen, ob eine Zahl eine Primzahl ist, müssen wir nur nach Faktoren suchen, die kleiner oder gleich der Quadratwurzel der zu prüfenden Zahl sind.

Primzahlen können niemals eine gerade Zahl sein, da gerade Zahlen alle durch 2 teilbar sind.

Außerdem können Primzahlen niemals eine gerade Zahl sein, da gerade Zahlen alle durch 2 teilbar sind.

Lassen Sie uns unter Berücksichtigung der obigen Ideen den Algorithmus verbessern:

public static List primeNumbersBruteForce(int n) { List primeNumbers = new LinkedList(); if (n >= 2) { primeNumbers.add(2); } for (int i = 3; i <= n; i += 2) { if (isPrimeBruteForce(i)) { primeNumbers.add(i); } } return primeNumbers; } private static boolean isPrimeBruteForce(int number) { for (int i = 2; i*i < number; i++) { if (number % i == 0) { return false; } } return true; } 

3.3. Verwenden von Java 8

Mal sehen, wie wir die vorherige Lösung mit Java 8-Redewendungen umschreiben können:

public static List primeNumbersTill(int n) { return IntStream.rangeClosed(2, n) .filter(x -> isPrime(x)).boxed() .collect(Collectors.toList()); } private static boolean isPrime(int number) { return IntStream.rangeClosed(2, (int) (Math.sqrt(number))) .filter(n -> (n & 0X1) != 0) .allMatch(n -> x % n != 0); } 

3.4. Verwendung von Sieatosthenes-Sieb

Es gibt noch eine weitere effiziente Methode, mit der wir Primzahlen effizient generieren können. Sie heißt Sieve Of Eratosthenes. Seine Zeiteffizienz ist O (n logn).

Werfen wir einen Blick auf die Schritte dieses Algorithmus:

  1. Erstellen Sie eine Liste aufeinanderfolgender Ganzzahlen von 2 bis n : (2, 3, 4,…, n)
  2. Zunächst sei p gleich 2, der ersten Primzahl
  3. Zählen Sie ab p in Schritten von p hoch und markieren Sie jede dieser Zahlen größer als p selbst in der Liste. Diese Zahlen sind 2p, 3p, 4p usw.; Beachten Sie, dass einige von ihnen möglicherweise bereits markiert wurden
  4. Suchen Sie die erste Zahl größer als p in der Liste, die nicht markiert ist. Wenn es keine solche Nummer gab, hören Sie auf. Andernfalls sei p jetzt gleich dieser Zahl (die die nächste Primzahl ist) und wiederhole ab Schritt 3

Am Ende, wenn der Algorithmus endet, sind alle Zahlen in der Liste, die nicht markiert sind, die Primzahlen.

So sieht der Code aus:

public static List sieveOfEratosthenes(int n) { boolean prime[] = new boolean[n + 1]; Arrays.fill(prime, true); for (int p = 2; p * p <= n; p++) { if (prime[p]) { for (int i = p * 2; i <= n; i += p) { prime[i] = false; } } } List primeNumbers = new LinkedList(); for (int i = 2; i <= n; i++) { if (prime[i]) { primeNumbers.add(i); } } return primeNumbers; } 

3.5. Arbeitsbeispiel für ein Sieb von Eratosthenes

Mal sehen, wie es für n = 30 funktioniert.

Betrachten Sie das obige Bild, hier sind die vom Algorithmus durchgeführten Durchgänge:

  1. Die Schleife beginnt mit 2, also lassen wir 2 unmarkiert und markieren alle Teiler von 2. Sie ist im Bild mit der roten Farbe markiert
  2. Die Schleife bewegt sich zu 3, also lassen wir 3 unmarkiert und markieren alle Teiler von 3, die noch nicht markiert sind. Es ist im Bild mit der grünen Farbe markiert
  3. Die Schleife bewegt sich auf 4, sie ist bereits markiert, also fahren wir fort
  4. Die Schleife bewegt sich auf 5, also lassen wir 5 unmarkiert und markieren alle Teiler von 5, die noch nicht markiert sind. Es ist im Bild mit der lila Farbe markiert
  5. Wir fahren mit den obigen Schritten fort, bis die Schleife erreicht ist, die der Quadratwurzel von n entspricht

4. Fazit

In diesem kurzen Tutorial haben wir Möglichkeiten aufgezeigt, wie wir Primzahlen bis zum Wert 'N' generieren können.

Die Implementierung dieser Beispiele finden Sie auf GitHub.