Java Prime Number check mit Benutzereingabe

Question

Ich habe gerade mit der Programmierung für College begonnen und ich musste ein Programm schreiben, das Benutzereingaben (Ganzzahlen) überprüft, ob sie eine Primzahl sind oder nicht.

Ich habe gute Ergebnisse bekommen, aber ich wollte nach Ihrer Meinung fragen und ob ich etwas vergessen habe.

package uebung_3; 


import java.util.Scanner; 

public class PrimZahlen { 

    public static void main(String[] args) { 

     System.out.print("Enter a number: "); 
     Scanner key = new Scanner(System.in); 
     int in = key.nextInt(); 

     prim(in); 
    } 

    private static void prim(int in) {//int in is a Scanner var. 
     if (in == 2 || in == 3) { 

      System.out.println(in + " is a prime number"); 
     } else if (in == 5 || in == 7) { 
      System.out.println(in + " is a prime number"); 
     } else if (in % 2 == 0 || in % 3 == 0) { 
      System.out.println(in + " is not a prime number."); 
     } else if (in % 5 == 0 || in % 7 == 0) { 
      System.out.println(in + " is not a prime number."); 
     } else { 
      System.out.println(in + " is a prime number."); 
     } 
    } 

} 

Answer 1

Sie es in einer mathematischen Weise tun können, und nicht nur bis prime überprüfen Faktor 7. Hier ist meine Lösung:

public static void main(final String[] args) { 
    System.out.print("Enter a number: "); 
    final Scanner key = new Scanner(System.in); 
    final int in = key.nextInt(); 

    if (isPrime(in)) { 
     System.out.println(in + " is a prime number"); 
    } else { 
     System.out.println(in + " is not a prime number"); 
    } 
} 

private static boolean isPrime(final int in) { 
    if (in < 2) return false; 

    for (int i=2; i <= Math.sqrt(in); i++){ 
     if (in%i == 0){ 
      return false; 
     } 
    } 
    return true; 
} 

Answer 2

Ihr Programm ist nicht korrekt. Das ist richtig Implementierung, die nun alle Integer-Zahlen von minus unendlich bis unendlich überprüfen unter Berücksichtigung 1 als Nicht-Primzahl:

public boolean isPrime(int number) { 
     if(number < 2) return false; 
     for(int i = 2; i <= Math.sqrt(number); i++) { 
      if(n % i == 0) { 
       return false; 
      } 
     } 
     return true; 
    } 

Answer 3

Sie shold überprüfen diese Zahl hat nur 2 devisors (1 und sich selbst).

Zum Beispiel:

static boolean isPrime(int n) { 
    for (int i = 2; i < n; i++) { 
     if (n % i == 0) 
      return false; 
    } 
    return true; 
} 

Bereich für Iteration (von 2 bis i^2 < = n) optimiert werden

Answer 4

Das größte Problem ist, dass Sie nicht Primfaktoren größer als 7 Überprüfung; Das bedeutet, dass Sie die falsche Antwort für n >= 121 bekommen werden.

Nur weil alle anderen im Grunde den gleichen Algorithmus vorgeschlagen hat, ist hier eine andere, die einfach zu implementieren ist: Sieve of Eratosthenes:

boolean isPrime(int n) { 
    if (n <= 0) return false; 

    // sieve is basically a boolean[], where each element will 
    // contain "true" if the number is prime, "false" otherwise. 
    BitSet sieve = new BitSet(n + 1); 
    sieve.set(0, n + 1); 

    // Zero isn't prime, nor is 1. 
    sieve.clear(0); sieve.clear(1); 

    for (int i = 2; i <= n; ++i) { 
    if (sieve.get(i)) { 
     // i is a prime number. 
     // Mark all multiples of i as non-prime. 
     for (int j = 2 * i; j <= n; j += i) { 
     sieve.clear(j); 
     } 
    } 
    } 

    // n is prime if the corresponding element in the sieve is "true". 
    return sieve.get(n); 
} 

Beachten Sie, dass dies so Faktor kann, dass Sie die sieveBitSet wiederverwenden können für mehrere Aufrufe an die Methode (speziell können Sie es wieder für einen kleineren Wert von n verwenden).

Answer 5

Primzahlen haben nur 2 Teiler die 1 und die Zahl selbst. Um zu überprüfen, ob eine Zahl prim ist oder nicht, müssen Sie alle möglichen Teiler dieser Zahl überprüfen. Zum Beispiel:

boolean isPrimeNumber(int num){ 
    if(num < 2) 
     return false; 
    for(int i = 2; i <= Math.sqrt(num); i++){ 
     if(num % i == 0){ 
      return false; 
     } 
    } 
    return true; 
} 

Answer 6

Der Wikipedia-Eintrag auf primality test einen besseren Algorithmus zum Testen gibt als bisher präsentiert, und wir können es in Java implementieren trivialer genug, um wie

private static boolean isPrime(int n) { 
    if (n <= 1) { 
     return false; 
    } else if (n <= 3) { 
     return true; 
    } else if (n % 2 == 0 || n % 3 == 0) { 
     return false; 
    } 
    int sq = (int) Math.ceil(Math.sqrt(n)); 
    for (int i = 5; i <= sq; i += 6) { 
     if (n % i == 0 || n % 2 + i == 0) { 
      return false; 
     } 
    } 
    return true; 
} 

und ändern Sie Ihre main Methode zu verwenden, es, etwas wie

// prim(in); 
if (isPrime(in)) { 
    System.out.printf("%d is prime.%n", in); 
} else { 
    System.out.printf("%d is not prime.%n", in); 
}