Ich verstehe nicht, diese ‚für‘ Schleife für Primzahl Validierung in Java

Question

ich das nicht verstehen ‚für‘ Schleife in Java

Diese Schleife nur zu prüfen ist, ob eine Zahl eine Primzahl ist oder nicht. Ich verstehe die erste Aussage, weil 1 keine Primzahl ist, sondern was in der 'for'-Aussage passiert. Warum wird 'primeNumber' durch zwei geteilt und warum ist das zweite 'if' für einen Rest von Null berechnet? Wie hilft dieser Code, eine Primzahl zu bestätigen? Was macht es?

public static boolean isPrime (int primeNumber) { 

    if (primeNumber == 1) { 
     return false; 
    } 

    for (int primeDivider=2; primeDivider <= primeNumber/2; primeDivider++) { 

     if (primeNumber % primeDivider == 0) { 
      return false; 
     } 

    } 

    return true; 

} 

Answer 1

Eine Primzahl kann nur durch sich selbst und eins geteilt werden. 7 ist prim, da nur 1 und 7 teilen sich in 7. Auch 8 nicht prim ist, weil sowie 1 und 8, beide 2 und 4 teilen sich in 8.

Blick auf die for Schleife und sehen, welche Werte primeDivider nimmt: 2 , 3, 4, 5, ... Die Schleife versucht jedes dieser wiederum, um zu sehen, ob es sich in die Nummer teilt, die Sie testen. Wenn es sich gleichmäßig teilt, mit einem Rest 0, dann ist die getestete Zahl nicht prim und die Methode gibt false zurück. Wenn keine der Zahlen sich teilt, wird die Zahl in prime getestet und die Methode gibt true zurück. Nebenbei, primeNumber ist ein schlechter Variablenname. Etwas wie possiblePrime wäre besser. Die getestete Nummer ist möglicherweise nicht prim.

Die primeDivider Sequenz stoppt bei der Hälfte der getesteten Anzahl. Wenn eine Zahl nicht prim ist (eine zusammengesetzte Zahl), dann ist garantiert mindestens einer ihrer Teiler kleiner oder gleich der Hälfte der Zahl.

Wie andere gesagt haben, ist dies kein sehr effizienter Test. Hier ist eine etwas effizientere Version für Sie zu studieren:

public static boolean isPrime (int possiblePrime) { 

    // Test negatives, zero and 1. 
    if (possiblePrime <= 1) { 
    return false; 
    } 

    // Test even numbers 
    if (possiblePrime % 2 == 0) { 

    // 2 is the only even prime. 
    return possiblePrime == 2; 

    } 

    // Test odd numbers >= 3. 
    int limit = possiblePrime/2; 
    for (int primeDivider = 3; primeDivider <= limit; primeDivider += 2) { 

    if (possiblePrime % primeDivider == 0) { 
     return false; 
    } 

    } 

    // Only prime numbers reach this point. 
    return true; 

} 

Durch die Behandlung ungerade und gerade getrennt Zahlen, können Sie alle geraden Zahlen mit einem einzigen Test zu fangen und durch primeDivider von 2 jedes Mal treten, halbieren etwa die Zeit für ungerade Zahlen.

Wie billjamesdev sagt, dass noch effizienter durch den Einsatz gemacht werden kann:

int limit = (int)Math.floor(Math.sqrt(possiblePrime)); 

Eine zusammengesetzte Zahl immer einen Divisor, andere als 1 hat

, weniger als oder gleich seine Quadratwurzel.