Primzahlprüfung

Question

Jede Primzahl hat die Form 6k + 1 oder 6k-1. Um zu überprüfen, ob eine Zahl prim ist oder nicht, können wir den folgenden Algorithmus verwenden. Ich habe Programme gesehen, die auf diesen Algorithmen basieren.

public boolean isPrime(int n) 
{ 

    if (n <= 1) return false; 
    if (n <= 3) return true; 

    if (n%2 == 0 || n%3 == 0) return false; 

    for (int i=5; i*i<=n; i=i+6) 
     if (n%i == 0 || n%(i+2) == 0) 
      return false; 

    return true; 
} 

Aber ich verstehe nicht, was das Problem gewesen wäre, wenn wir Code in folgenden Weise geschrieben hatten:

public boolean isPrime(int number){ 
     boolean primeFlag = false; 
     if(number == 0 || number ==1){ 
      return primeFlag; 
     } 
     if(number == 2 || number == 3){ 
      primeFlag = true; 
     } 
     if((number+1)%6 == 0){ 
      primeFlag = true; 
     } 
     if((number-1)%6 == 0){ 
      primeFlag = true; 
     } 
     return primeFlag; 
    } 

Damit wir die Zeit, die Komplexität reduzieren O (1) im Vergleich zu O (Wurzel (n)). Bitte lassen Sie mich wissen, wenn es in die falsche Richtung geht.

Answer 1

Es ist korrekt zu sagen, dass jede Primzahl (außer 2 und 3) einen Rest von 1 oder 5 hat, wenn sie durch 6 geteilt wird (siehe für eine tiefere Erklärung). Das Gegenteil ist jedoch nicht wahr. Nicht jede Zahl, die einen Rest von 1 oder 5 hat, wenn sie durch 6 geteilt wird, ist eine Primzahl.

Nehmen Sie 35 zum Beispiel. Es hat einen Rest von 5, wenn es durch 6 geteilt wird, aber es ist kein Prime (35 = 5 x 7).