[Java] Finde die Primzahl mit dem Eratostenes-Sieb (Teil 2)

Einführung

Der Code von vorheriger Beitrag ist ein kostenintensiver Code, der "die gesamte Liste durchsucht, teilt und durchsucht", wie von @swordone hervorgehoben. Es stellte sich heraus. Basierend auf dem Hinweis von @swordone habe ich den Code grundlegend korrigiert.

Code

Die Unterschiede zum vorherigen Code sind wie folgt.

• Die Suchliste wurde von "List " in "boolean []" geändert.
• Anstelle von "Liste von 2 bis zur Obergrenze" wird "Liste der Indizes von 2 bis zur Obergrenze" verwendet.
• Erstens werden alle Elemente des Arrays als Primzahlen behandelt (true), und wenn sie herausgefiltert werden, werden sie als nicht primäre Werte behandelt (false).
• Geändert zu "Zufälliger Zugriff auf das Element des zu überprüfenden und zu überprüfenden Werts" anstelle von "Durchsuchen der gesamten Liste, Teilen und Sieben".
• Durch Erhöhen des Inkrements der for-Anweisung um "Erhöhung um den Wert der aktuellen Primzahl (firstNum)" anstelle von "Erhöhung um 1" wird nur das Vielfache der aktuellen Primzahl (firstNum) herausgefiltert.

PrimeNumberFinder.java

static void printPrimeNumbers2(int maxNumber) {

	//Schritt 1: Fügen Sie "Ganzzahl von 2 bis Obergrenze" in die Suchliste ein.
	boolean[] targetNumbers = new boolean[maxNumber + 1];
	Arrays.fill(targetNumbers, true);
	targetNumbers[0] = false;
	targetNumbers[1] = false;

	//Primzahlliste
	List<Integer> primeNumbers = new ArrayList<Integer>();

	int sqrt = (int) Math.sqrt(maxNumber);

	//Schritt 3: Setzen Sie den Siebvorgang fort, bis der erste Wert in der Suchliste die Quadratwurzel des Arguments erreicht.
	for(int i=2; i<=sqrt; i++) {
		//Schritt 2: Machen Sie die erste Zahl in der Suchliste zu einer Primzahl und zeigen Sie Vielfache aus der Suchliste an.
		//* Zu diesem Zeitpunkt ist die bereits ausgeblendete Nummer (false) ausgeschlossen.
		int firstNum = i;
		if (targetNumbers[i]) {
			for (int j=i*firstNum; j<targetNumbers.length; j+=firstNum) {
				targetNumbers[j] = false;
			}
		}
	}

	//Schritt 4: Verschieben Sie die in der Suchliste verbleibenden Werte in die Primzahlenliste und beenden Sie den Vorgang.
	for (int i=2; i<targetNumbers.length; i++) {
		if (targetNumbers[i]) {
			primeNumbers.add(i);
		}
	}

	//Anzeige von Primzahlen
	System.out.println(primeNumbers.stream().map(pNum -> pNum.toString()).collect(Collectors.joining("\t")));
}

Wie schnell war es

• Es war mehr als zehnmal schneller als der vorherige Code.
• Auch wenn Sie nicht General Gillen sind, ist es ein Unterschied, der Sie dazu bringt zu sagen: "Ist es nicht überwältigend, meine Armee?"

Zusammenfassung

• Durch diesen Code wurde ich daran erinnert, dass eine Entwicklung, die den "Berechnungsbetrag" berücksichtigt, wichtig ist.
• Ich denke, es gibt noch einige Punkte, die mit diesem Code verbessert werden können ...
• Danke @swordone für alle Hinweise.