# Primzahltest rekursiv



## buffy2299s (19. Jun 2017)

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 (19. Jun 2017)

Moin,


buffy2299s hat gesagt.:


> 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 (19. Jun 2017)

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


----------



## stg (19. Jun 2017)

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 (19. Jun 2017)

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 (19. Jun 2017)

buffy2299s hat gesagt.:


> 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.


buffy2299s hat gesagt.:


> 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 %


buffy2299s hat gesagt.:


> 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 (19. Jun 2017)

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 (19. Jun 2017)

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 (19. Jun 2017)

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 (19. Jun 2017)

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


----------



## stg (19. Jun 2017)

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

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


----------



## buffy2299s (19. Jun 2017)

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


----------



## stg (19. Jun 2017)

buffy2299s hat gesagt.:


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



Probiers doch einfach mal aus....


----------



## buffy2299s (19. Jun 2017)

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 (19. Jun 2017)

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 (20. Jun 2017)

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


----------

