Java Primzahl boolean?

Ich muss eine Klassenmethode schreiben istPrim(long zahl), die true für eine positive Primzahl zurückgibt und false, falls die Zahl nicht prim ist.

Die Verwendung von main(), println(), und Scanner() ist nicht erlaubt.

Das hier ist der Code, den ich geschrieben habe. Sieht der richtig aus? Wenn nicht, was kann ich hier verbessern?

  public static boolean istPrim(long zahl) {
    boolean primZahl = true;
    long moeglicherTeiler = 2L;
  
    while (moeglicherTeiler < zahl) { // Teiler muss kleiner sein als Zahl selbst
      if (n % moeglicherTeiler == 0) { // Teiler gefunden -> keine Primzahl
        primZahl = false;
      }
  
      moeglicherTeiler = moeglicherTeiler + 1; // Teiler hochzählen
    }
  
    return primZahl;
  }
}

Answer 1

[Isendrak]

1. Der höchstmögliche Wert für einen Teiler wäre die Quadratwurzel von "zahl".
2. Du könntest zu Anfang überprüfen, ob "zahl" gerade und ungleich 2 ist, dann sparst du dir für den Fall alle weiteren Tests.
3. Beginne "moeglicherTeiler" mit dem Wert 3 und erhöhe beim Hochzählen um 2.
4. Pack das return direkt unter das if, dann sparst du dir unnötige Schleifendurchläufe.
5. Zahlen, die kleiner als 2 sind, sind keinesfalls Primzahlen. Überprüfe das vor der Schleife.

Eine stark optimierte Version könnte z.B. so aussehen:

public static boolean istPrim(long zahl) {
    //2 ist die kleinste (und einzige) gerade Primzahl
    if(zahl < 2) return false;
    if(zahl == 2) return true;
    //Alle anderen geraden Zahlen sind keine Primzahlen
    if(zahl & 1 == 0) return false;
    //Es reicht aus, bis zur Quadratwurzel von "zahl" zu testen
    long hoechsterTeiler = Math.sqrt(zahl);
    //3 ist die erste Primzahl nach der 2
    //"moeglicherTeiler" wird in jedem Durchlauf um 2 erhöht, denn gerade Teiler sind bereits ausgeschlossen
    for(long moeglicherTeiler = 3; moeglicherTeiler <= hoechsterTeiler; moeglicherTeiler += 2)
        //Wenn sich "zahl" ohne Rest durch "moeglicherTeiler" teilen lässt, dann ist "zahl" keine Primzahl
        if(zahl%moeglicherTeiler==0) return false;
    //Wenn der Code hier ankommt, dann ist "zahl" eine Primzahl
    return true;
}

Answer 2

[kmkcl]

Dein Ansatz ist richtig - ließe sich jedoch noch kräftig optimieren. 😉

Du brauchst z.B. nur bis Wurzel(Zahl) hochzählen, wenn es einen Teiler gibt kann er nämlich maximal so groß sein. Außerdem kannst du in der Schleife gleich in der if-Bedingung return false schreiben. Somit sparst du Rechenzeit. Nur als kleine Anregungen ;)

Answer 3

[Nube4618]

Du brauchst nur bis Zahl/2 zu prüfen. Es gibt noch weitere Optimierungsmöglichkeiten, wenn die Zahl z.Bsp. Nicht durch 2 Teilbar ist, kannst du eh alle geraden Teiler weglassen....

Woher ich das weiß: Berufserfahrung

Answer 4

[fabberlin]

du musst rückwärts zählen von der gewünschen zahl bis 1. wenn die zahl nur durch sich selbst oder 1 teilbar ist, dann ist eine primzahl. ansonsten abbrechen und primzahl false