Rekursionsproblem bei Primzahlfunktion

[SheldoN]

Hallo liebes Forum,
ich habe ein Problem bzgl. dieses Quellcodes:

package nummer1;
import java.util.*;
public class Prim {
	
	public static void main(String[] args)	{
		
		System.out.println("Bitte geben Sie eine Primzahl ein.");
		Scanner sc = new Scanner(System.in);
		int prim = sc.nextInt();
		
		System.out.println(succPrim(prim));
	}
	
	
	static int succPrim(int prim)	{
		prim++;
		if(prim == 2)	{
			return 3;
		} else if(prim % 2 == 0){
			succPrim(prim);
		} else {
			for(int i = 3; i < prim; i = i + 2)	{
				if(prim % i == 0)	{
					succPrim(prim);
				}
			}
                        return prim;
		}
                return prim;
	}
}

... und zwar soll er, nach eingegebener Zahl, die nächste Primzahl ausgeben. Leider führt der Block succPrim die Rekursion nicht aus und gibt direkt prim++ aus. Hat jemand einen Tipp für mich?

 

[nillehammer]

Die Verzweigungen habe ich jetzt nicht gendanklich alle durchgespielt. Aber irgendwo müsstest Du den return-Wert der rekursiv aufgerufenen Methode succPrim einer Variablen zuweisen, mit Der Du weiterarbeitest oder direkt irgendwo

return succPrim

hinschreiben. Auch das

prim++

scheint mir suspekt. Das gehört meiner Meinung nach ganz weg und dann lieber beim normalen und rekursiven Aufruf ein

prim + 1

als Parameter übergeben.

 

[SheldoN]

ich habs jetz nochma neu gemacht... funktioniert aber immer noch nicht

package nummer1;
import java.util.*;
public class Prim {
	
	public static void main(String[] args)	{
		
		System.out.println("Bitte geben Sie eine Primzahl ein.");
		Scanner sc = new Scanner(System.in);
		int prim = sc.nextInt();
		
		int nPrim = succPrim(prim + 1);
		System.out.println("Die nächste Primzahl lautet: " + nPrim);
	}
	
	
	static int succPrim(int prim)	{
		if(prim == 2)	{
			return 3;
		} else if(prim % 2 == 0){
			succPrim(prim + 1);
		} else {
			for(int i = 3; i < prim; i = i + 2)	{
				if(prim % i == 0)	{
					succPrim(prim + 1);
				}
			}
			return prim;
		}
		return prim;
	}
}

jemand evtl. andere Vorschläge?

 

[nillehammer]

Wie gesagt, Du musst innerhalb der Methode auch irgendwie den return-Value der rekursiven Aufrufe verarbeiten oder direkt returnen. Sonst läuft er durch alle Verzweigungen durch, und am Ende gibt er das prim aus, so wie es beim ersten Aufruf übergeben wurde.

 

[SheldoN]

Kannst du mir evtl. nen kleines Beispiel zeigen? Ich weiß grad irgendwie nicht, wie das gemeint ist.

 

[nillehammer]

Habe meine Erklärungen zum Besseren Verständnis als Kommentare in den Code eingefügt:

    static int succPrim(int prim)   {
        if(prim == 2)   {
            return 3;
        /* Hier testest Du offensichtlich, ob prim eine gerade Zahl ist,
         * wenn ja, rufst Du zwar rekursiv die Methode auf, machst aber
         * nichts mit dem Ergebnis. Das ist so gut, wie die Methode garnicht
         * aufrufen. Nach Abarbeitung dieses Zweiges springt er nämlich -->
         */
        } else if(prim % 2 == 0){ 
            succPrim(prim + 1);
        } else {
            for(int i = 3; i < prim; i = i + 2) {
                if(prim % i == 0)   {
                    succPrim(prim + 1);
                }
            }
            return prim;
        }
        /* --> Hier hin und gibt prim so aus, wie beim ersten Aufruf übergeben.*/
        return prim;
    }

Als Tipp, versuch mal in einer Methode

boolean isPrim(int zahl)

die Überprüfungen, ob zahl eine Primzahl ist, zu bündeln. Diese Überprüfung stellst Du dann an den Anfang der Methode

succPrim

. Das vereinfacht sie zu folgendem Code:

    static int succPrim(int prim)   {
        // Abkürzung bei 2
        if(prim == 2)   {
            return 3;
        }
        // Abbruchbedingung für Rekursion am besten am Anfang
        if (isPrim(prim)) {
          return prim;
        }
        // Rekursiver Aufruf
        return succPrim(prim + 1); 
    }

 

[SheldoN]

Ah okay vielen dank. Schön erklärt ! Wieder was gelernt dank dir!
Leider darf ich keine Methoden verwenden. Ich muss aus eigener Hand überprüfen ob die Zahlen Primzahlen sind. Ich bin noch am Anfang

 

[Sesostris]

	public static int succPrime(int prime) {
		prime++;
		if (prime == 2 || prime == 3)
			return prime;
		if (prime % 2 == 0)
			return succPrime(prime);
		for (int i=3; i<=Math.sqrt(prime); i+=2)
			if (prime % i == 0) return succPrime(prime);
		return prime;
	}

Der Quellcode, den du zuallererst gepostet hast, ist dem eigentlich schon ziemlich nahe gekommen. Nur die Basisfälle waren nicht korrekt und die returns teilweise an den falschen Stellen.
Du musst übrigens keine Primzahl eingeben, sondern eine beliebige Zahl reicht aus. Es wird dir dann die nächstgrößere Primzahl zurückgegeben.