Problem bei Primzahltest Rekursion

Status
Nicht offen für weitere Antworten.

Helex

Mitglied
Hallo,

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

Code:
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!
 

Helex

Mitglied
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

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

Helex

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

Wildcard

Top Contributor
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

Mitglied
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

Top Contributor
Also dazu passt dein Code nun überhaupt nicht.
Code:
int j = 2;
Bei jedem Methodeneintritt wird j neu intialisiert, das kann schonmal nicht gehen
Code:
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.
Code:
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

Mitglied
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

Top Contributor
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

Mitglied
@ wildcard,

vielen tausendmal dank, du hast mir die Augen geöffnet: Mein fertiger Code sieht nun so aus
Code:
	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!
 
Status
Nicht offen für weitere Antworten.

Neue Themen


Oben