C Primzahlen rekursiv dastellen

[WirJun]

Hallo Leute,

ich habe die Aufgabe ein Programm zu schreiben, dass alle Primzahlen im Intervall [1,N] (N wird vom Benutzer eingegeben) ausgibt. Die Iterative Methode habe ich bereits erledigt, nur bei der rekursiven Methode steh ich ein bisschen an. Kann mir vielleicht jemand einen Tipp zum Starten geben?

Ich poste hier mal meine Lösung für die Iterative Methode:

#include <stdio.h>
#include <stdlib.h>

int main(void) {
	int n, i, x;
	printf("Primzahlen im Intervall [1, N] mit der Iterative Methode\n");
	printf("Bitte geben Sie N-Zahl für das Intervall ein: ");
	scanf("%d\n", &n);
	for (x = 3; x <= n; x++) {
		for (i = 2; i < x; i++) {
			if (x%i == 0) break;
		}
		if (i == x) printf("%i ist eine Primzahl\n", x);
	}
	return EXIT_SUCCESS;
}

Danke für eure Hilfe )

 

[DjNDB]

Ist bei mir schon etwas her, aber du könntest es mit dieser Funktionssignatur probieren:
bool restlosTeilbar(int x)
Und dann überlegen was da drin rekursiv passieren muss.

Für eine interessantere und effizientere iterative Lösung kannst du dir mal das "Sieb des Eratosthenes" anschauen.

 

[Plaste]

Mit

if (x%i!=0) restlosTeilbar(int x);

die Rekursion einleiten. In der Funktion halt nach Faktoren zerlegen.

Viel zu überlegen ist da nicht

 

[DjNDB]

Hier ging es darum einen Tipp zu geben. Ich habe absichtlich nicht die fertige Lösung gegeben, damit er es lernen kann.

 

[WirJun]

ich glaube mein Hauptproblem ist, dass ich noch nicht verstanden habe was ein rekursive Methode macht. Wir habe zwar in den Vorlesungen ein paar Beispiele durchgemacht aber die Funktionsweise ist mir noch schleierhaft.

 

[DjNDB]

Das ist auch anfangs etwas seltsam. Meine Sichtweise:
Du schreibst eine Funktion, und verwendest diese Funktion in sich selbst, als würde sie bereits funktionieren.

Du verstehst es am besten, indem du es selbst implementierst. Im zweifel schau auch nach anderen Quellen die es erklären.

In der Praxis wirst du sowas wahrscheinlich nicht häufig sehen.
In diesem Fall kannst du damit auch schnell 'nen stack overflow bekommen, wenn du N zu groß wählst.

 

[convexus]

Realisiere z.B. die Funktion

 bool ist_nicht_teilbar_durch_zahlen_im_bereich(int zahl, int von, int bis)

. Die Rekursion bekommst im Wsesentlichen du mit der Definition ist_nicht_teilbar_durch_zahlen_im_bereich(zahl, von, bis) = zahl%von!=0 && ist_nicht_teilbar_durch_zahlen_im_bereich(zahl, von+1, bis). Hier fehlen noch die Bedingungen zur Terminierung. Eine ungerade Zahl z ist dann eine Primzahl, wenn ist_nicht_teilbar_durch_zahlen_im_bereich(z, 2, z-1) wahr ist.

 

[asdfman]

In diesem Fall kannst du damit auch schnell 'nen stack overflow bekommen, wenn du N zu groß wählst.

Nicht zwangsläufig. Rekursion benötigt nicht immer einen Stack und dann kann man auch beliebig hohe Werte benutzen.
Siehe hier: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1

In contrasting iteration and recursion, we must be careful not to confuse the notion of a recursive process with the notion of a recursive procedure. [...] It may seem disturbing that we refer to a recursive procedure such as fact-iter as generating an iterative process. However, the process really is iterative: Its state is captured completely by its three state variables, and an interpreter need keep track of only three variables in order to execute the process.

 

[BadBigBen]

Dein Programmschnipsel ist fehlerhaft, eine Primzahl wird übersprungen...

 

[WirJun]

Dein Programmschnipsel ist fehlerhaft, eine Primzahl wird übersprungen...

Welche denn?

 

[asdfman]

Such dir mal eine Liste von Primzahlen und guck ziemlich am Anfang.

 

[WirJun]

Ok den Fehler habe ich ausgebessert, aber auf die rekursive Methode komm ich trotzdem nicht. Wie lang soll den der Code ungefähr werden, ich hab immer noch keine Ahnung wie das gehen soll^^

 

[BadBigBen]

So wie ich es verstanden habe, was gefordert wird, musst du einen Code erzeugen der von der Eingabe rückwärts zu 0 geht und alle Primzahlen dann ausspuckt...

Hier mal nen kleinen Ausschnitt, der dir rekursiv ein wenig erklärt am Beispiel einer SUM Funktion, Link darunter wo es her kommt damit du auch den ganzen Text lesen kannst.

For better visualization of recursion in this example:

sum(5)
=5+sum(4)
=5+4+sum(3)
=5+4+3+sum(2)
=5+4+3+2+sum(1)
=5+4+3+2+1+sum(0)
=5+4+3+2+1+0
=5+4+3+2+1
=5+4+3+3
=5+4+6
=5+10
=15

Every recursive function must be provided with a way to end the recursion. In this example when, n is equal to 0, there is no recursive call and recursion ends.

quelle: http://www.programiz.com/c-programming/c-recursion

und schaue auch mal diesen Code an, einmal mit 'recursion' und einmal ohne:

Prime number program in c using recursion
http://www.cquestions.com/2011/08/prime-number-program-in-c-using.html

 

[WirJun]

Ich habe jetzt noch einmal ein bisschen herumprobiert und bin auf ein vorläufiges Ergebnis gekommen, das Problem ist nur dass ich keine Ausgabe habe..
Ich poste einfach mal den Code:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>


bool IsPrime(int candidate) { // Test whether the parameter is a prime number.
		
	if ((candidate & 1) == 0) {
	    if (candidate == 2)  {
		return true;
	    }
	    else {
		return false;
	    }
	}
	return EXIT_SUCCESS;
}

int main(void) {    //Write prime numbers between 0 and N
	printf("Bitte geben Sie N-Zahl für das Intervall ein: ");
	int n;	
	scanf("%d\n", &n);	
	printf("--- Primes between 0 and %d ---\n", n);
	
	for (int i = 0; i < 100; i++) {
	    bool prime = IsPrime(i);
	    if (prime)
		printf("Prime: %d", i);
		
	}
	return EXIT_SUCCESS;
}

Der Code ist noch fehlerhaft, ich bekomme nämlich keine Ausgabe^^

 

[Nase]

Und ist auch keine Rekursion.

 

[kuddlmuddl]

Oben hast du noch geschrieben, dass du mehrere Beispiele hast und diese auch behandelt wurden.. ist dir da nie etwas aufgefallen? Eine Gemeinsamkeit? Also die Eigenschaft, die Rekursion auszeichnet und von anderen Ansätzen unterscheidet?
Es geht darum, dass eine Funktion SICH SELBST aufruft.
Was auch immer du oben programmiert hast: IsPrime ruft nicht IsPrime innerhalb {} auf und kann daher auch keine Rekursion sein.
Außerdem verstehe ich nicht so ganz die Hilflosigkeit.. hier zu fragen ist natürlich legitim da du es ja auch selbst versuchst und Code postest aber bist du noch nicht auf die Idee gekommen die beiden Wörter Rekursion und Primzahl zu googlen? Da kommen wirklich genug Lösungen - was ja auch zu erwarten war bei einer so typischen Anfänger-Aufgabe.

Die Idee ist, dass die Funktion IsPrime zwei Argumente hat: Einmal natürlich die zu prüfende Zahl und außerdem genau einen Teiler, der in diesem Schritt der Rekursion geprüft werden soll. Dh die Funktion prüft genau eine einzige Zahl ob sie teilt oder ruft sich selbst auf mit dem Befehl eine weitere Zahl zu probieren.

Also zB in Pseudo-Code der für 2 nicht funktioniert:

bool PruefePrim(int candidate)
{
  return IsPrime(candidate, 3); // Wir reichen die Entscheidung weiter und beginnen mit dem ersten Versuch candidate zu teilen mit 3;
}

bool IsPrime(int candidate, int aktuellerVersuch)
{
  if (aktuellerVersuch > sqrt(candidate))
    return true; // Hier wurde die eine mögliche Entscheidung getroffen: Da der aktuelle Versuch den größten möglichen Teiler überschritten hat, muss kein weiterer Teiler Untersucht werden.
  if (aktuellerVersuch teilt candidate ohne Rest)
    return false; // Hier ist die andere mögliche Entscheidung getroffen worden: candidate kann keine Primzahl sein, da sie ohne Rest Teilbar ist.
  return IsPrime(candidate, aktuellerVersuch +2; // Dies ist die spannende Rekursions-Zeile. Wir rufen erneut IsPrime auf aber diesmal ändern wir das zweite Argument! Dh es konnte in diesem Durchlauf keine Entscheidung getroffen werden aber es gibt noch weitere Kandidaten die getestet werden müssen.
}

Du musst dir das am besten mal aufschreiben was ich oben angedeutet habe:
PruefePrim(10)
=> IsPrime(10, 3) wird aufgerufen
=> weder if 1 noch if 2 also erneuter Aufruf
=> IsPrime(10, 5) wird aufgerufen
=> Das eine if trifft zu => wir beenden die Rekursion

PruefePrim(7)
=> IsPrime(7, 3) wird aufgerufen
=> weder if 1 noch if 2 also
=> IsPrime(7, 5) wird aufgerufen
=> Das andere if trifft zu => wir beenden die Rekursion

 

[WirJun]

Danke an alle die mir geholfen haben, das Programm ist nun fertig. Bin froh, dass es noch ein paar Leute gibt, die ihre Zeit opfern und anderen helfen.

LG

 

[asdfman]

Kuddlmuddl: Danke für das schöne Beispiel, in dem eine rekursive Funktion keinen rekursiven Prozess erzeugt. Werde es bookmarken, falls wieder einer mit Stack Overflow ankommt :3
€: Weniger Dank dafür, OP die Hausaufgaben gemacht zu haben

 

[Plaste]

hui, ich war viel zu spät, daher ist mein Beispiel jetzt gelöscht

 

[Miuwa]

in dem eine rekursive Funktion keinen rekursiven Prozess erzeugt. Werde es bookmarken, falls wieder einer mit Stack Overflow ankommt

Weißt du zufälliger weise, ob man sich auf diese Optimierung "verlassen" kann?
Ich kanns mir zwar vorstellen, hab mich aber noch nie getraut es drauf ankommen zu lassen.