Primzahltest rekursiv

[buffy2299s]

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?

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);
        }
    }

}

 

[VfL_Freak]

Moin,

aber das Stimmt noch nicht so ganz

und das heißt was ?? 🙄
http://www.java-forum.org/forum-faq-beitraege/7407-man-fragen-richtig-stellt.html
VG Klaus

 

[buffy2299s]

Naja das es mir auch Zahlen ausgibt die keine Primzahlen sind.

 

[stg]

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]

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]

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]

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]

Hab bis jetzt das mal gemacht:

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]

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]

Hm ok, und wie führ ich bei einer rekursion die Abbruchbedingung ein?

 

[stg]

Du hast doch schon mehrere drin. Du brauchst nur noch die passende für m..

if(m==...) return ...

 

[buffy2299s]

naja die wäre ja dann eigentlich if(m==1) return false oder?

 

[stg]

naja die wäre ja dann eigentlich if(m==1) return false oder?

Probiers doch einfach mal aus....

 

[buffy2299s]

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]

Eine deiner Abbruchbedingungen lautet

} 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]

Als kleiner Tipp (Pseudocode):

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);
}