Wie zu bestimmen, ob eine Zahl ist prime

Question

Okay, mein Problem ist weniger, wie herauszufinden, ob eine Nummer ist Prime, weil ich denke, dass ich herausgefunden, aber mehr davon, wie es richtig angezeigt wird.

Hier ist mein Code:

public static void main(String[] args) { 
    // Declare Variables 
    int randomNumbers = 0; 
    int sum = 0; 
    //Loop for number generation and print out numbers 
    System.out.print("The five random numbers are: "); 
    for (int i = 0; i <= 4; i++) 
    { 
     randomNumbers = (int)(Math.random()*20); 
     sum += randomNumbers; 

     if (i == 4) { 
      System.out.println("and " + randomNumbers + "."); 
     } 
     else { 
      System.out.print(randomNumbers + ", "); 
     } 
    } 
    //Display Sum 
    System.out.println("\nThe sum of these five numbers is " + sum + ".\n"); 

    //Determine if the sum is prime and display results 
    for(int p = 2; p < sum; p++) { 
     if(sum % p == 0) 
      System.out.println("The sum is not a prime number."); 
     else 
      System.out.println("The sum is a prime number."); 
     break; 
     } 
    } 


} 

Nun mein Problem ist, wenn die Zahl endet so etwas wie 9 zu sein, es wird sagen, dass es eine Primzahl ist, die es nicht ist. Ich denke, das Problem ist, dass die Unterbrechung es nach einer Schleife stoppt, so dass es Variable p nicht erhöht, so testet es nur Division durch 2 (denke ich). Wenn ich jedoch den Unterbrechungspunkt entferne, wird bei jedem Durchlauf "Die Summe ist/ist keine Primzahl" ausgedruckt, bis sie die Schleife verlässt. Ich bin mir nicht sicher, was ich hier machen soll.

Answer 1

Ihre Methode zum Finden, ob Ihre Nummer prim ist, ist die richtige Methode. Um es so zu machen, dass es nicht konsistent ausdruckt, ob die Zahl prim ist oder nicht, könnten Sie eine externe Variable haben, die angibt, ob die Zahl prim ist oder nicht.

Wie

boolean prime = true; 
    for (int p = 2; p < sum; p++) { 
     if (sum % p == 0) { 
      prime = false; 
      break; 
     } 
    } 
    if (prime) 
     System.out.println("The sum is a prime number."); 
    else 
     System.out.println("The sum is not a prime number."); 

Durch dieses Verfahren wird das Programm tun wird übernehmen die Zahl prim ist, bis er das falsch erweist. Wenn es also feststellt, dass es nicht prim ist, setzt es die Variable auf false und bricht aus der Schleife aus.

Dann, nachdem die Schleife beendet ist, müssen Sie nur drucken, ob die Nummer prime war oder nicht.

Eine Möglichkeit, diese Schleife schneller zu machen, besteht darin, von p = 2 zu p zu gehen, wenn p = Quadratwurzel der Summe ist. So mit dieser Methode Ihre for-Schleife wird wie folgt aussehen:

double sq = Math.sqrt((double)sum); 
    for (int p = 2; p < sq; p++) { 
     //Rest of code goes here 
    } 

this helps

Answer 2

Sie müssen speichern, ob die Zahl prim ist in einem boolean außerhalb der Schleife:

//Determine if the sum is prime and display results 
boolean isPrime = true; 
for(int p = 2; p < sum; p++) { 
    if(sum % p == 0){ 
     isPrime = false; 
     break; 
    } 
} 
if(isPrime){ 
    System.out.println("The sum is a prime number."); 
} else { 
    System.out.println("The sum is not a prime number."); 
} 

Answer 3

Sie haben Recht, derzeit teilen sich Ihre Code-Tests durch zwei, und der Break-Befehl stoppt nach einer Schleife.

Nach dem ersten Durchlauf Ihrer Schleife (p == 2) stoppt die break immer die Schleife.

boolean isPrime=true; 
for(int p = 2; p < sum; p++) { 
    if(sum % p == 0) { 
     isPrime=false; 
     System.out.println("The sum is not a prime number."); 
     break; 
    } 
} 
if (isPrime) 
    System.out.println("The sum is a prime number."); 

Dieser Code kann verbessert Effizienz und für die Code-Eleganz werden:

Die schnellste Lösung, um Ihren Code wird das Schleifenteil wie folgt zu ändern.

Für die Effizienz müssen Sie die Teilbarkeit nicht mit allen Zahlen überprüfen, die kleiner als die Summe sind. Es reicht aus, alle Zahlen mit der Quadratwurzel der Summe zu vergleichen.

Für besseren Code, erstellen Sie eine separate Funktion, um zu testen, ob eine Zahl prim ist.

Hier ist ein Beispiel, das beide implementiert.

// tests if n is prime 
public static boolean isPrime(int n) { 
    if (n<2) return false; 
    for(int p = 2; p < Math.sqrt(n); p++) { 
     if(n % p == 0) return false; // enough to find one devisor to show n is not a prime 
    } 
    return true; // no factors smaller than sqrt(n) were found 
} 

public static void main(String []args){ 
    ... 
    System.out.println("sum is "+ sum); 
    if (isPrime(sum)) 
     System.out.println("The sum is a prime number."); 
    else 
     System.out.println("The sum is not a prime number."); 
} 

Answer 4

So viele Antworten wurden bisher veröffentlicht, die korrekt sind, aber keiner von ihnen optimiert ist. Deshalb habe ich mir überlegt, den optimierten Code zu teilen, um hier die Primzahl zu bestimmen. Bitte werfen Sie einen Blick auf das folgende Code-Snippet ...

private static boolean isPrime(int iNum) { 
boolean bResult = true; 
if (iNum <= 1 || iNum != 2 && iNum % 2 == 0) { 
    bResult = false; 
} else { 
    int iSqrt = (int) Math.sqrt(iNum); 
    for (int i = 3; i < iSqrt; i += 2) { 
    if (iNum % i == 0) { 
     bResult = false; 
     break; 
    } 
    } 
} 
return bResult; 
} 

Vorteile von oben Code-:

1. Es ist für negative Zahlen arbeiten werde und 0 & 1 als auch.
2. Es wird die for Schleife nur für ungerade Zahlen ausgeführt.
3. es wird die Schleifenvariable for um 2 eher zu erhöhen als 1.
4. es wird die for Schleife nur bis Quadratwurzel Zahl anstatt bis zu Nummer iterieren.

Explanation-:

Ich habe die vier Punkte über dem genannten ich eins nach dem anderen erklären werde. Der Code muss entsprechend für die ungültigen Eingänge geschrieben werden und nicht nur für den gültigen Eingang. Welche Antworten bisher geschrieben wurden, sind auf einen gültigen Eingabebereich beschränkt, in dem die Nummer iNum >=2 steht.

sollten wir uns bewusst sein, dass nur ungerade Zahlen Primzahl sein kann, Note-: 2 ist die einzige gerade Primzahl. So müssen wir for Schleife für gerade Zahlen nicht ausführen.

Wir müssen nicht for Schleife für gerade Werte der Variablen i ausführen, da wir wissen, dass nur gerade Zahlen durch gerade Zahl geteilt werden können. Ich habe bereits im obigen Punkt erwähnt, dass nur ungerade Zahlen mit Ausnahme von 2 als gerade Primzahlen sein können. So keine Notwendigkeit, Code innerhalb for Schleife für gerade Werte der Variablen i in for.

Wir sollten iterieren for Schleife nur bis Quadratwurzel der Nummer statt upto Nummer. Nur wenige der Antworten haben diesen Punkt umgesetzt, aber ich dachte trotzdem, es hier zu erwähnen.

Answer 5

kleine Primzahlen

Verwenden Apache Commons MathPrimzahltest wird Verfahren zur Primzahlen im Bereich von int bezogen. Sie finden den Quellcode unter GitHub.

<dependency> 
    <groupId>org.apache.commons</groupId> 
    <artifactId>commons-math3</artifactId> 
    <version>3.6.1</version> 
</dependency> 

// org.apache.commons.math3.primes.Primes 
Primes.isPrime(2147483629); 

Es verwendet den Miller-Rabin probabilistischen Test in einer solchen Weise, dass ein Ergebnis gewährleistet ist: es verwendet die firsts Primzahlen als aufeinanderfolgende Basis (siehe Handbook of Applied Cryptography von Menezes, table 4.1/Seite 140) .

Big Primzahlen

Wenn Sie Primzahlen suchen größer als Integer.MAX_VALUE:

1. Verwenden BigInteger#isProbablePrime(int certainty), vor der Überprüfung der Hauptkandidat

   Gibt true zurück, wenn dieser BigInteger ist wahrscheinlich prim, falsch, wenn es definitiv zusammengesetzt ist. Wenn die Gewissheit ≤ 0 ist, wird Wahr zurückgegeben. Parameter: Gewissheit - ein Maß für die Unsicherheit, die der Aufrufer bereit ist zu tolerieren: Wenn der Aufruf wahr zurückgibt, ist die Wahrscheinlichkeit, dass dieser BigInteger Primzahl ist, größer (1 - 1/2 Sicherheit). Die Ausführung Zeit dieser Methode ist proportional zum Wert dieses Parameters.

2. Nächste Verwendung "AKS Primality Test", um zu überprüfen, ob der Kandidat wirklich prime ist.