# Problem bei Primzahltest Rekursion



## Helex (5. Dez 2006)

Hallo,

die iterative Variante ist ja kein Problem, aber bei der Rekursion spuckt mir meine Methode immer etwas falsches aus:


```
public static boolean primRek (int n){
		
		int j = 2;
		// trivialer Fall
		if (n == 2) {
			
			return true;
		}  
		if (n % j == 0 ){
			
			return false;
			
		} else if( j >= Math.sqrt(n)) {	
			
			return primRek(n & j++);
		}  
		
		return true;
	}
```

Bei Methodenaufruf: primRek(597) kommt true heraus, obwohl es durch 3 teilbar ist. Wird eventuell die Variable j++ bei meinen rekursiven Aufruf nicht inkrementiert?

Danke für eure Ratschläge!


----------



## Wildcard (5. Dez 2006)

was willst du den mit & j++ erreichen?  ???:L


----------



## Helex (5. Dez 2006)

Mit j++ soll beim erneuten Aufruf j (also der Teiler) um 1 erhöht werden, so geht man nach und nach alle Zahlen durch bis entweder eine Teiler gefunden ist der mit der zu testenden Zahl den Rest 0 hat und ist dann somit keine Primzahl.

Das ist also meine Idee dahinter


----------



## Wildcard (5. Dez 2006)

j++ erhöht j.
Aber warum die bitweise 'Verundung' mit n?
Kein mir bekannter Algorithmus funktioniert so.


----------



## Helex (5. Dez 2006)

Das scheint wohl so zu sein, jedenfalls knobble ich schon eine Weile herum und es will einfach nicht so recht klappen!


----------



## Wildcard (5. Dez 2006)

Was scheint wohl so zu sein? Weißt du wirklich was & macht?
Versuch mal den Algorithmus den du verwenden willst als Pseudocode zu schreiben, dann helfe ich dir das umzusetzen.


----------



## Helex (5. Dez 2006)

Programm primRek (n)

Hilfsteiler h = 2
*Falls* eingegebene Zahl(n)  modulo j = 0

    so gib keine Primzahl aus

* Falls* h kleiner als die Qaudratwurzel von n ist

   so rufe primRek áuf und erhöhe Hilfsteiler 

Falls der zweite Fall nicht mehr erfüllt ist, so gib (n) ist Primzahl aus.


----------



## Wildcard (5. Dez 2006)

Also dazu passt dein Code nun überhaupt nicht.

```
int j = 2;
```
 Bei jedem Methodeneintritt wird j neu intialisiert, das kann schonmal nicht gehen

```
else if( j >= Math.sqrt(n))
```
Wird nur ausgeführt wenn der Hilfsteiler *größer* ist als  die Quadratwurzel der Zahl, also genau falsch rum.

```
n & j++
```
 Und das hier macht etwas GANZ anderes als du im Sinn hattest:
Du verundest auf bit-Ebene n und j (wodurch eine völlig neue Zahl entsteht) und inkrementierst anschließend j um 1  :autsch:


----------



## Helex (5. Dez 2006)

Hmm das mit dem neuinitialisieren der Variable macht Sinn und das mit dem & auch.  Also ist mein Ansatz doch nicht so richtig... ich werd nochmal nach denken.

Wenn ich primRek(n, j++) schreibe, so liest es Java als Parameter der Funktion, den es nicht gibt)


----------



## Wildcard (5. Dez 2006)

Das ist richtig, daher musst du entweder einen 2ten Paramter einführen (dann müsste es allerdings ++j heißen  :wink: ), oder du speicherst dir j in einer Klassenvariablen.


----------



## Helex (5. Dez 2006)

@ wildcard,

vielen tausendmal dank, du hast mir die Augen geöffnet: Mein fertiger Code sieht nun so aus

```
static int h = 2;
	

public static boolean primRek (int n){
		
		
		// trivialer Fall
		if (n == 2) {
			
			return true;
		}  
		if (n % h == 0 ){
			
			return false;
			
		} else if( h <= Math.sqrt(n)) {	
			
			//static int j++ = p;
			h++;
			return primRek(n);
		}  
		
		return true;
	}
```

und funktioniert einwandfrei

Noch einen schönen Abend!


----------

