Kann mir bitte jemand erklären, wie diese Implementierung funktioniert? Und kann sie verbessert werden? Wie?

Question

public class Main { 
    public static void main(String args []){ 
        long numberOfPrimes = 0; //Initialises variable numberOfPrimes to 0 (same for all other variables)
        int number = 1; 
        int maxLimit = 10000000; 
        boolean[] sieve = new boolean[maxLimit]; //creates new boolean array called sieve and allocates space on the
                                                //stack for this array which has maxLimit spaces in it 
        for ( int i = 2; i < maxLimit; i++ ) { //for statement cycling from 2 to 10000000, does not execute the rest
                                              //of the block if the boolean value in the array is true 
            if ( sieve[i] == true ) continue; 

            numberOfPrimes++; //otherwise it increments the number of prime numbers found

            if ( numberOfPrimes == 10001 ) {  //if 10001st prime number is found, break from loop
                number = i; 
                break; 
            } 

            for ( int j = i+i; j < maxLimit; j += i ) //do not understand the point of this loop logically
                sieve[j] = true;                      //testing if the value in the array is true again?
        } 
        System.out.println("10001st prime: "+ number); 
    } 
    }

Ich verstehe nicht wirklich, was in diesem Programm vor sich geht und hoffe, dass es mir jemand erklären kann. Ich habe die spezifischen Zeilen kommentiert, die mir Probleme bereiten bzw. die ich verstehe, was die Zeilen tun sollen. Vielen Dank für all die Hilfe! :)

Answer 1

Machen Sie sich vertraut mit Eratosthenes-Sieb Algorithmus. Wikipedia hat sogar ein animiertes Gif, das den Prozess demonstriert. Und Ihr Code ist nur eine unkomplizierte Umsetzung davon.

Answer 2

Ja, dies ist die grundlegende Implementierung des Siebs von Eratosthenes. Es gibt eine ganze Reihe von Möglichkeiten, wie Sie es verbessern können, aber lassen Sie uns zuerst das Grundprinzip durchgehen.

Sie erstellen ein Array mit booleschen Werten. Der INDEX im Array steht für die Zahl, die wir daraufhin prüfen, ob sie eine Primzahl ist oder nicht.

Nun werden Sie jede Zahl daraufhin überprüfen, ob sie eine Primzahl ist. Zunächst einmal lautet die Definition einer Primzahl: "Alle Zahlen, die NUR durch sich selbst und 1 teilbar sind, ohne Bruchrechnung".

for ( int i = 2; i < maxLimit; i++ )

Man beginnt mit dem INDEX 2 (der Zahl 3), denn je nach Definition sind 1 und 2 immer Primzahlen. (Einige Definitionen besagen, dass 1 keine Primzahl ist).

if ( sieve[i] == true ) continue;

Wenn eine Zahl zuvor als Nicht-Primzahl markiert wurde, wird die aktuelle Iteration nicht durchgeführt.

numberOfPrimes++;

        if ( numberOfPrimes == 10001 ) {
            number = i; 
            break; 
        }

Wenn der INDEX, bei dem wir uns gerade befinden, noch nicht als Primzahl markiert wurde, muss es eine sein, also erhöhen wir die Anzahl der gefundenen Primzahlen. Der nächste Teil des Codes gehört vermutlich zu den Anforderungen des Programms, die besagen, dass das Programm beendet werden muss, wenn 10001 Primzahlen gefunden wurden. Dieser Teil kann weggelassen werden, wenn Sie tatsächlich nach Primzahlen bis zur festgelegten Höchstzahl suchen wollen, anstatt nach einer bestimmten Anzahl von Primzahlen.

for ( int j = i+i; j < maxLimit; j += i )
            sieve[j] = true;

Hier beginnt der eigentliche Zauber des Siebs. Nach der Definition einer Primzahl kann eine Zahl keine Primzahl sein, wenn sie durch etwas anderes als sich selbst und 1 teilbar ist. Daher können wir für jede neue Zahl, die wir finden und die eine Primzahl ist, alle ihre Faktoren als NICHT prim markieren. Ein Beispiel: Bei der ersten Iteration der for-Schleife beginnen wir mit 3. Da sieve[2] falsch ist (noch nie besucht), ist sie eine Primzahl (UND 3 IST EINE PRIMME!). Dann können alle anderen Faktoren von 3 KEINE Primzahlen sein. Die oben erwähnte for-Schleife geht durch das gesamte Sieb und markiert alle Faktoren von 3 als falsch. Diese Schleife macht also: sieve[5] = true; sieve[8] = true ... bis zum Ende des Siebes.

Wenn Sie nun die erste Zahl erreichen, die größer ist als der ursprünglich festgelegte Höchstwert, können Sie sicher sein, dass jede Zahl, die einen Faktor hat, als nicht primär markiert wurde. Am Ende haben Sie ein boolesches Array, in dem jeder Index, der als falsch markiert ist, eine Primzahl darstellt.

Auf Wikipedia finden Sie wahrscheinlich eine viel bessere Beschreibung, aber das ist die Quintessenz. Hoffentlich hilft es!

Answer 3

for ( int j = i+i; j < maxLimit; j += i ) //dont understand the point of this loop logically
                sieve[j] = true;          //testing if the value in the array is true again ?

Es handelt sich nicht um eine Prüfung, sondern um eine Einstellung. Diese Schleife setzt alle Elemente im Array mit Indizes, die ein Vielfaches von i a true . Wenn i 2 ist, dann werden die Positionen 4, 6, 8 ... auf true . Wenn i 3 ist, werden die Positionen 6, 9, 12 ... auf true und so weiter.

Und wie Sie aus dem ersten Satz ersehen können if ,

if ( sieve[i] == true ) continue; 

... alle Artikel, die true entsprechen den Nicht-Primzahlen.

Answer 4

Ich finde, der einfachste Weg, etwas zu verstehen, ist, es zu dekonstruieren. Gehen wir also die Schleife ein paar Mal durch, ja?

Anbruch der ersten Iteration

- 9999998 Werte verbleiben -

i = 2
sieve[2] est false so dass wir in der aktuellen Iteration weitermachen.
numberOfPrimes = 1 und so setzen wir die Verarbeitung fort
Setzen Sie jedes Vielfache von 2 auf true en sieve[] .

Anbruch der zweiten Iteration

- 9999997 Werte verbleiben -

i = 3
sieve[3] est false so dass wir in der aktuellen Iteration weitermachen.
numberOfPrimes = 2 und so setzen wir die Verarbeitung fort
Setzen Sie jedes Vielfache von 3 auf true en sieve[] .

Anbruch der dritten Iteration

- 9999996 Werte verbleiben -

i = 4
sieve[4] est true (aus der ersten Iteration). Zur nächsten Iteration springen.

usw... aber in diesem Fall stürzt der Mond nicht in Termina .

Answer 5

Die betreffende Schleife ist nicht Überprüfung für wahre Werte, ist es Einstellung wahre Werte.

Sie geht durch jedes Vielfache der Primzahl und markiert es als Nicht-Primzahl bis zu maxLimit . Sie werden feststellen, dass der Code keine weiteren mathematischen Berechnungen enthält, um festzustellen, was eine Primzahl ist und was nicht.