Java Programm zur Überprüfung von Primzahlen mit Beispiel

Was ist eine Primzahl?

Eine Primzahl ist eine natürliche Zahl größer als 1, die nur durch 1 oder sich selbst teilbar ist. Beispielsweise ist 11 nur durch 1 oder sich selbst teilbar. Weitere Primzahlen sind 2, 3, 5, 7, 11, 13, 17 usw. Die Folge ließe sich unendlich fortsetzen.

Eine Zahl größer als 1, die keine Primzahl ist, nennt man zusammengesetzte Zahl, da sie aus kleineren Teilern zusammengesetzt werden kann. Die Zahl 9 ist zusammengesetzt, weil sie durch 3 teilbar ist, und 15 ist zusammengesetzt, weil sie durch 3 und 5 teilbar ist.

Hinweis: 0 und 1 sind keine Primzahlen. 2 ist die einzige gerade Primzahl, und negative Werte gelten niemals als Primzahlen.

Wie man prüft, ob eine Zahl eine Primzahl ist Java

Die Verifizierungsstrategie ist ein einfacher Teilbarkeitstest. Man nimmt den Kandidatenwert, teilt ihn nacheinander durch jede kleinere ganze Zahl und prüft den Rest, den der Modulo-Operator zurückgibt. Ein Rest von null beweist, dass ein Teiler existiert, wodurch die Zahl sofort disqualifiziert wird.

Programmlogik:

• Wir müssen eine Eingabezahl, beispielsweise 17, durch die Zahlen von 2 bis 17 teilen und den Rest überprüfen. Ist der Rest 0, ist die Zahl keine Primzahl.
• Keine Zahl ist durch mehr als die Hälfte ihrer selbst teilbar. Also müssen wir Schleife durch gerade numberToCheck/2Wenn die Eingabe 17 ist, ist die Hälfte 8.5 und die Schleife durchläuft die Werte von 2 bis 8.
• Wenn die zu prüfende Zahl durch eine andere Zahl vollständig teilbar ist, wird das Flag isPrime gesetzt. false und die Schleife wird verlassen.

Two Java Die Merkmale tragen den gesamten Algorithmus. Der Modulo-Operator % gibt den Rest einer Ganzzahldivision zurück, und die break Die Anweisung beendet die Schleife, sobald das Ergebnis bekannt ist, sodass keine unnötigen Iterationen ausgeführt werden.

Java Programm zur Überprüfung, ob eine Zahl eine Primzahl ist oder nicht

Das folgende Programm weist der Variablen `numberToCheck` den Wert 17 zu und gibt jeden Divisionsschritt aus, sodass Sie die Logik Zeile für Zeile nachvollziehen können. Der Code ist editierbar. Ändern Sie also den Wert und führen Sie das Programm mit einer zusammengesetzten Zahl wie z. B. 21 erneut aus, um das gegenteilige Ergebnis zu sehen.

public class PrimenumberToCheckCheck {

 public static void main(String[] args) {
  int remainder;
  boolean isPrime=true;
  int numberToCheck=17; // Enter the number you want to check for prime

  //Loop to check whether the number is divisible by any number other than 1 and itself
  for(int i=2;i<=numberToCheck/2;i++)
  {
   //number is divided by i
            remainder=numberToCheck%i;
            System.out.println(numberToCheck+" Divided by "+ i + " gives a remainder "+remainder);

       //if remainder is 0 then the number is not prime and we break the loop. Else continue the loop
     if(remainder==0)
     {
        isPrime=false;
        break;
     }
  }
  // Check value true or false, if isPrime is true then the number is prime otherwise not prime
  if(isPrime)
     System.out.println(numberToCheck + " is a Prime number");
  else
     System.out.println(numberToCheck + " is not a Prime number");
    }
  }

Erwartete Ausgabe:

17 Divided by 2 gives a remainder 1
17 Divided by 3 gives a remainder 2
17 Divided by 4 gives a remainder 1
17 Divided by 5 gives a remainder 2
17 Divided by 6 gives a remainder 5
17 Divided by 7 gives a remainder 3
17 Divided by 8 gives a remainder 1
17 is a Prime number

Die Schleife stoppt bei 8, da 17 geteilt durch 2 in der Ganzzahlarithmetik 8 ergibt. Da der Rest nie null war, behält das Flag „isPrime“ seinen Anfangswert „true“, und die letzte Bedingung gibt das positive Ergebnis aus.

Optimierte Primzahlprüfung mittels Quadratwurzelmethode

Das Teilen bis zur Hälfte der Zahl ist zwar korrekt, aber ineffizient. Wenn eine Zahl n einen Teiler hat, der größer als ihre Quadratwurzel ist, muss der zugehörige Teiler kleiner als die Quadratwurzel sein; er wäre also bereits gefunden worden. Die Überprüfung bis √n liefert daher mit deutlich weniger Iterationen dasselbe Ergebnis.

public class PrimeCheckOptimized {

    public static boolean isPrime(int n) {
        // 0, 1 and negative values are never prime
        if (n <= 1) {
            return false;
        }
        // 2 is the only even prime number
        if (n == 2) {
            return true;
        }
        if (n % 2 == 0) {
            return false;
        }
        // test only odd divisors up to the square root
        for (int i = 3; i * i <= n; i += 2) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[] samples = {1, 2, 9, 17, 97};
        for (int value : samples) {
            System.out.println(value + " is prime: " + isPrime(value));
        }
    }
}

Ausgang:

1 is prime: false
2 is prime: true
9 is prime: false
17 is prime: true
97 is prime: true

Die Bedingung i * i <= n Dadurch wird ein Aufruf von `Math.sqrt` für Gleitkommazahlen vermieden, und die Schrittweite von 2 überspringt jeden geraden Teiler. Bei einem Wert wie 1,000,003 benötigt die Standardschleife etwa 500,000 Iterationen, während diese Version weniger als 500 benötigt.

Überprüfen Sie die vom Benutzer eingegebene Primzahl.

Fest codierte Eingaben sind für Demonstrationen praktisch, in realen Übungen wird jedoch üblicherweise die Eingabe über die Tastatur benötigt. Die Scanner-Klasse liest eine Ganzzahl von der Konsole und übergibt sie an dieselbe isPrime-Methode.

import java.util.Scanner;

public class PrimeCheckUserInput {

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

        boolean isPrime = number > 1;
        for (int i = 2; i * i <= number; i++) {
            if (number % i == 0) {
                isPrime = false;
                break;
            }
        }

        System.out.println(number + (isPrime ? " is a Prime number" : " is not a Prime number"));
        sc.close();
    }
}

Beispielausführung:

Enter a number: 29
29 is a Prime number

Häufige Fehler beim Schreiben eines Primzahlenprogramms

Die meisten fehlerhaften Eingaben scheitern an Grenzwerten und nicht in der Hauptschleife. Die folgende Liste enthält die häufigsten Fehler in Anfängercode.

1. Die Schleife beginnt bei 1: Jede ganze Zahl ist durch 1 teilbar, daher wird das Flag sofort auf „false“ gesetzt und das Programm meldet, dass keine Zahl eine Primzahl ist.
2. 1 als Primzahl behandeln: Der Wert 1 hat nur einen Teiler, erfüllt also nicht die Definition mit zwei Teilern und muss daher false zurückgeben.
3. Weglassen der break-Anweisung: Das Programm liefert zwar immer noch die richtige Antwort, wiederholt sich aber auch nach Bekanntwerden des Ergebnisses immer wieder, was bei großen Eingaben Zeitverschwendung bedeutet.
4. Die Verwendung von i <= n als die Grenze: Die Zahl teilt sich immer selbst, daher muss die Schleife vor Erreichen von n stoppen.
5. Vergleichen mit = statt ==: Ein einzelnes Gleichheitszeichen weist einen Wert zu, anstatt ihn zu prüfen, was zu einem Kompilierfehler in der if-Bedingung führt.

Vergleich von Primzahlprüfungsmethoden

Wählen Sie die Methode, die zur Größe der Eingabe und dazu passt, ob ein einzelner Wert oder ein ganzer Bereich getestet werden soll.

Wenn ein ganzer Bereich anstatt eines einzelnen Wertes klassifiziert werden muss, ist das Siebverfahren weitaus effizienter. Unser Begleitprogramm hilft Ihnen dabei. Prim Numbers von 1 um 100 Dies veranschaulicht dieses Muster. Weitere verwandte Übungen mit Schleifen finden Sie in der Dokumentation. Fibonacci-Folge in Java, hat das Java Palindromprogrammund die Bubble Sortieralgorithmus in JavaAnfänger, die eine Auffrischung zum Thema Flaggen- und Zähleranzeige benötigen, sollten Folgendes lesen: Java Variablen im Wesentlichen Java Lernprogramm.

Häufig gestellte Fragen