So finden Sie Java-Primzahlen

Was ist eine Primzahl?

Wenn ich versuche, das Problem der Wettkampfprofis herauszufordern, kann ich mich nicht erinnern, was ich als Student gelernt habe.

Was ist laut Wikipedia eine Primzahl?

Eine Primzahl ist eine natürliche Zahl, die größer als 1 ist und nur 1 positiven Bruch und sich selbst hat. Es kann als natürliche Zahl umformuliert werden, bei der die Anzahl der positiven Brüche 2 beträgt.

Korrekt. Mit anderen Worten, es ist eine ganze Zahl größer als ** 1, eine Zahl, die nur durch 1 und sich selbst geteilt werden kann **.

Programm zur Beurteilung der Primzahl

import java.util.Scanner;

public class PrimeNumber {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int target = sc.nextInt();

    if (target < 2) {
      System.out.println(target + "Ist keine Primzahl.");
      return;
    }

    for (int i = 2; i < target; i++) {
      if (target % i == 0) {
        System.out.println(target + "Ist keine Primzahl.");
        return;
      }
    }
    
    System.out.println(target + "Ist eine Primzahl.");
  }
}

Kommentar

Eine ganze Zahl größer als 1

    if (target < 2) {
      System.out.println(target + "Ist keine Primzahl.");
      return;
    }

Hier prüfen wir, ob die Ganzzahl größer als ** 1 ist, was von Bedeutung ist, da es sich um eine Primzahl ** handelt. Wenn es weniger als 2 ist, wissen Sie, dass es sich nicht um eine Primzahl handelt. Geben Sie sie also aus und beenden Sie den Vorgang sofort.

Eine Zahl, die nur durch 1 und sich selbst geteilt werden kann

Schließlich wird dieser Teil zum Herzen.

    for (int i = 2; i < target; i++) {
      if (target % i == 0) {
        System.out.println(target + "Ist keine Primzahl.");
        return;
      }
    }
    
    System.out.println(target + "Ist eine Primzahl.");

Teilen Sie in der for-Anweisung die Zahl von 2 nach target-1 nacheinander und prüfen Sie, ob sie teilbar ist. Wenn es nur eine teilbare Zahl gibt, ist diese Zahl keine Primzahl. Geben Sie sie also aus und beenden Sie den Vorgang mit "return".

Wenn es keine teilbare Zahl gibt, ist "Ziel" eine Primzahl. : klatschen:

Beschleunigen

Um herauszufinden, ob es sich um eine Primzahl handelt, habe ich die obige Methode zum Teilen durch 1 und alle Zahlen mit Ausnahme der Zielzahl verwendet. Bei dieser Methode dauert die Berechnung jedoch umso länger, je größer die Anzahl der zu untersuchenden Objekte ist.

Wie Sie in den Kommentaren gesagt haben, können Sie anscheinend beurteilen, ob es sich um eine Primzahl handelt oder nicht, indem Sie nur die Werte unter der Quadratwurzel überprüfen.

Warum bis zur Quadratwurzel?

Eine Primzahl war eine Zahl, die nur durch 1 und sich selbst teilbar war, aber andere Zahlen werden zusammengesetzte Zahlen genannt. Mit anderen Worten, eine zusammengesetzte Zahl ist eine Zahl, die weder 1 noch eine Primzahl ist. Mit anderen Worten ist die zusammengesetzte Zahl ** 1 und hat mindestens einen anderen Bruch als sich selbst **.

Zusätzlich hat die Anzahl der Verbundwerkstoffe die Eigenschaft, dass ** einen Bruchteil von ** √n oder weniger aufweist.

Die Anzahl der Verbundwerkstoffe hat einen Bruchteil von √n oder weniger

Warum können wir sagen, dass die zusammengesetzte Zahl einen Bruchteil kleiner als √n hat?

Erstens kann die zusammengesetzte Zahl n als "n = ab" ausgedrückt werden, da es natürliche Zahlen a und b gibt, die nicht 1 sind. Wenn n keinen Bruch hat, der kleiner oder gleich √n ist, dann ist √n <a, √n <b. Da √n größer als 0 ist, ist √n√n (= n) ab, wenn √n <a, √n <b` (wenn n keinen Bruchteil kleiner oder gleich √n hat). Es wird kleiner als "n = ab" sein. Daher kann gesagt werden, dass n einen Teiler von √n oder weniger hat.

Mit anderen Worten, wenn n eine zusammengesetzte Zahl ist, hat sie einen Teiler von √x oder weniger. Wenn Sie also prüfen, ob es einen Teiler unter √x gibt, Sie können feststellen, ob die Zahl eine Primzahl ist!

Kai / Primzahl-Beurteilungsprogramm

import java.util.Scanner;

public class PrimeNumber {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int target = sc.nextInt();

    if (target < 2) {
      System.out.println(target + "Ist keine Primzahl.");
      return;
    }
    if (target % 2 == 0) { //Die gerade Zahl kehrt zuerst zurück
      System.out.println(target + "Ist keine Primzahl.");
      return;
    }

    for (int i = 3; i <= Math.sqrt(target); i+=2) {
      if (target % i == 0) {
        System.out.println(target + "Ist keine Primzahl.");
        return;
      }
    }

    System.out.println(target + "Ist eine Primzahl.");
  }
}