Problem bei Primzahltest Rekursion

[Helex]

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]

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

 

[Helex]

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]

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

 

[Helex]

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

 

[Wildcard]

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]

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]

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]

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]

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]

@ 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!