Primzahltest rekursiv

buffy2299s

Mitglied
Hei Leute,

ich muss einen Primzahltest mittels Rekursion durchführen, jedoch darf ich keinerlei Schleifen innerhalb des Tests benutzen. Das hab ich bis jetzt, aber das Stimmt noch nicht so ganz, kann mir bitte jemand helfen?
Code:
public class Primzahl {
   
    public static void main(String [] args){
       
       
        for(int i = 0; i <= 200; i++){
            int zahl = i;
       
        if(method(zahl)==true){
            System.out.println("Ihre Zahl : "+ i + " ist eine Primzahl");
        }
        //else{
            //System.out.println("Ihre Zahl : "+ i + " ist keine Primzahl");
        //}
        }
    }
         static boolean method(int zahl){
             int i = 2;
        if(zahl == 1 || zahl == 0){
            return false;
        }
        else if( zahl == 2){
            return true;
        }
       
        if(zahl%i==0){
            return false;
        }
        else if(i > zahl/i){
            return true;   
        }
        else{
            return method(i+1);
        }
    }

}
 

stg

Top Contributor
Versuch doch mal in Worten zu beschreiben, wie du (rekursiv) vorgehen könntest, um zu prüfen, ob eine Zahl prim ist.
Gelingt dir das?
 

buffy2299s

Mitglied
Naja ich müsste ja prüfen ob die Zahl x mehrere Teiler hat. Sprich wenn sie mehr als 2 hat ist sie schon keine Primzahl mehr. Also müsste mein rekursiver aufruf ja so sein das ich x/y mach und dann immer y-1 nehme.
 

stg

Top Contributor
Naja ich müsste ja prüfen ob die Zahl x mehrere Teiler hat. Sprich wenn sie mehr als 2 hat ist sie schon keine Primzahl mehr.
Das sind ja nicht irgendwelche Teiler, die eine Primzahl hat, sondern zwei ganz bestimmte. Und zwar 1 und die Zahl selbst. Das sind aber Teiler einer jeden Zahl, müssen also nicht gesondert geprüft werden. Interessant sind nur die potentiellen Teiler im Bereich von 2 bis x-1.
Also müsste mein rekursiver aufruf ja so sein das ich x/y mach und dann immer y-1 nehme.
Was ist bei dir nun y?
Ferner ist das Ergebnis der Division x/y nicht von sonderlich großen Interesse. Wann ist y denn ein Teiler von x? Salopp formuliert: Wenn der ganzzahlige Rest ... Und dafür gibt es in Java den Modulo-Operator %
Also müsste mein rekursiver aufruf ja so sein das ich x/y mach und dann immer y-1 nehme.
Du müsstest deiner Methode also auch das aktuelle y übergeben, richtig?!
 

buffy2299s

Mitglied
Genau ich muss ja die Zahl x nur % mit den zahlen 2 bis x-1 nehmen. Und falls da irgendwann einmal eine null kommt, ist es ja schon keine Primzahl mehr. Das heißt das die zahl x immer gleich bleibt aber die zahl y immer um eins steigt bis x-1. Nur darf aber meine Methode nur x übergeben und nicht y und da hab ich ein problem
 

buffy2299s

Mitglied
Hab bis jetzt das mal gemacht:

Code:
public static boolean method(int zahl) {
        return method(zahl, zahl - 1);
    }
   
    private static boolean method(int zahl, int m) {
         if(zahl==0||zahl==1){
                return false;
            }
            if (zahl % m == 0) {
                return false;
                } else if (m > zahl/m) {
                return true;
                } else {
                return method(zahl,m-1);
                } 


}
 

stg

Top Contributor
Der Ansatz sieht schon ok aus.
Die Prüfung, ob zahl = 0 oder 1 ist kannst du bereits in die erste Methode einfließen lassen, sonst führst du sie ja in jedem Durchlauf aufs neue aus.
In der zweiten Methode fehlt dir die Abbruchbedingung. Du läufst sonst immer bis m=1 durch, und hast mit der 1 dann natürlich einen Teiler gefunden.
Außerdem schau noch mal, was du denn nun mit true und false wirklich meinst..
 

buffy2299s

Mitglied
mhm das Problem ist das es bei mir in eclipse eh ganze zeit anzeigt es sei keine primzahl, aber an sich stimmt der code ja schon. Aber ich glaube das if(m==1) return false, nicht richtig ist
 

DrZoidberg

Top Contributor
Eine deiner Abbruchbedingungen lautet
Java:
} else if (m > zahl/m) {
    return true;
also wenn m grösser ist als die Wurzel von zahl, dann ist es eine Primzahl.
Das ist aber nur dann korrekt, wenn m hochgezählt wird und nicht runter.
D.h. Du solltest zuerst testen ob die Zahl durch 2 teilbar ist. Danach setzt du m auf 3 und erhöhst m dann bei jedem rekursiven Aufruf um 2.
 

Flown

Administrator
Mitarbeiter
Als kleiner Tipp (Pseudocode):
Code:
def isPrime(n : Int) : Boolean = {
  if(n < 2) false;
  else isPrime(n, 2, sqrt(n).intValue);
}

def isPrime(n : Int, i : Int, limit : Int) : Boolean = {
  if(i > limit) true;
  else if(n % i == 0) false;
  else isPrime(n, i == 2 ? i + 1 : i + 2, limit);
}
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
M Wie könnte man den Codeschnipsel rekursiv darstellen? Allgemeine Java-Themen 1
M Endrekursiv vs Rekursiv Allgemeine Java-Themen 4
Aboya Kugel mit Hilfe von Dreiecken rekursiv zeichnen Allgemeine Java-Themen 2
Aboya Char Array rekursiv vergleichen Allgemeine Java-Themen 15
H Heron Verfahren Tail-rekursiv lösen Allgemeine Java-Themen 7
Kingamadeus2000 Alle mehrfach vorkommenden Buchstaben rekursiv aus einem String entfernen. Allgemeine Java-Themen 6
I Diskussion zu: Tribonacci Folge Rekursiv Allgemeine Java-Themen 15
R Warum ist die Methode unendlich oft rekursiv? Allgemeine Java-Themen 5
D 2,3-Baum rekursiv erstellen Allgemeine Java-Themen 20
denny86 NetBeans Ordnernamen rekursiv auslesen und in Variable verarbeiten Allgemeine Java-Themen 38
B Primfaktorzerlegung Rekursiv Allgemeine Java-Themen 2
S Verkettete (Teil)Liste sortieren ( rekursiv bis n) Allgemeine Java-Themen 2
L Alle möglichen Additionen (Rekursiv) Allgemeine Java-Themen 3
N Rekursiv Höhe Baum Allgemeine Java-Themen 3
H Vektor rekursiv erzeugen Allgemeine Java-Themen 2
J Breitensuche in Graph rekursiv Allgemeine Java-Themen 2
E ordner rekursiv durchsuchen Allgemeine Java-Themen 6
E Ordner rekursiv kopieren Allgemeine Java-Themen 8
R synchronized methode rekursiv aufrufen Allgemeine Java-Themen 5
S MergeSort iterativ und rekursiv? Allgemeine Java-Themen 8
G Array rekursiv durchlaufen Allgemeine Java-Themen 2
S JAVA JTree rekursiv umschreiben Allgemeine Java-Themen 5
leifg Rekursiv mit Threads Programmieren Allgemeine Java-Themen 2
sparrow Ant build-files rekursiv aus ant aufrufen Allgemeine Java-Themen 3
K zinsen rekursiv/iterativ Allgemeine Java-Themen 17
K Verzeichnis rekursiv aus JAR-Datei extrahieren Allgemeine Java-Themen 6
F Filelisting iterativ, nicht rekursiv Allgemeine Java-Themen 7
L Spielerei: Frame rekursiv darstellen Allgemeine Java-Themen 3
M Rekursiv Verzeichnisse ansehen und auf Muster matchen Allgemeine Java-Themen 6

Ähnliche Java Themen

Neue Themen


Oben