rekursion

Hi, hab mit c++ gestern angefangen zuvor scala bisschen geproggt.
Ich möchte n Primzahltester schreiben via rekursion.
Ausgabe von 1 bedeutet ist prim und Ausgabe von 2 ist keine prim.

Facts:
// prim(Zahltest, startwert, speicher)
// primzahlen <5 werden korrekt angezeigt
// nicht primzahlen >4 werden korrekt angezeigt
// 4 wird als prim identifiziert
// Primzahlen > 5 resultieren in Programmabsturz

Mein Ziel ist es ein Programm zu schreiben, dass sobald 3mal f%n = 0 auftritt keine Prim vorliegen kann-> abbruch +meldung.

#include <iostream>

using namespace std;

int prim(int f, int n, int m)
{
	if (f <= 1) { return(2); }
	if (f > 1 && f < 4){ return(1); }
	if (m > 2)  { return(2); }
	if (m == 2 && f == n) { return(1); }
	if ((f % n) == 0) { return(prim(f, n+1,m+1)); }
	else { return(prim(f,n+1,m)); }

}

int main()
{
   cout << "8: " <<prim(8,1,0) << endl; 

 return(0);
}

volkard

Ich habe keine Ahnung, was Du da anstellst.
Würde ich es rekursiv versuchen, dann wohl so:

#include <iostream>

using namespace std;

bool istPrim(unsigned int kandidat, unsigned int teiler)
{
	if(kandidat<2)
		return false;
	if(kandidat==2)
		return true;
	if(kandidat%teiler==0)
		return false;
	if(teiler*teiler>kandidat)
		return true;
	return istPrim(kandidat,teiler+1);
}

int main()
{
	for(unsigned int kandidat=0; kandidat<=20; ++kandidat)
		if(istPrim(kandidat,2))
			cout<<kandidat<<'\n';
	return((((0))));
}

So wie ich das verstehe, sollen da alle Teiler gezählt werden - inklusive 1 und f selbst. In diesem Fall muss aber n bis f + 1 laufen, um den letzten Teiler auch noch zu zählen - weil das nicht geschieht, wird 4 als Primzahl erkannt.

Damit dürfte auf einen Schlag auch der Absturz behoben sein, der sich daraus ergibt, dass m bei einer Primzahl erstmalig 2 wird, wenn n = f + 1 ist - du läufst, weil du auf f == n && m == 2 prüfst, da in eine Endlosschleife, die für jeden Durchlauf einen Stapelrahmen anlegt, und irgendwann läuft der Stack halt über.

Wie Volkard allerdings richtig anmerkt, gibt es sinnvollere Implementationsmöglichkeiten - eigentlich ist schon Rekursion hier eine ziemlich schräge Wahl, aber diese Drei-Teiler-Nummer habe ich bisher noch nirgends gesehen.

volkard

seldon schrieb:

aber diese Drei-Teiler-Nummer habe ich bisher noch nirgends gesehen.

Es gibt da angeblich den Präzidenzfall des BWLers, der sagte, "3 ist prim, 5 ist prim, 7 ist prim, so geht das natürlich weiter". Warum muß ich jetzt an unseren Bundeskanzlerin denken?

Diese Drei-Teiler-Nummer ist mir neu. Eine andere Drei-Teiler-Theorie taucht durchaus oft auf. Man testet gegen 2, 3 und 5. Wer überlebt, ist eine Primzahl. Zwischen 1 und 5 Prozent der Ersttäter machen das beim Primzahlenschießen, schätze ich. Eigentlich Quatsch, aber zusammen mit dem Programmierenlernen und der seltsamen Programmiersprache stürmt da auf einmal zu viel auf einen ein und man hat nicht mehr alles im Blick. Ich kenne keinen, der das Problem nicht hat und sich nicht mal dabei erwischt, daß er beim Einarbeiten in ein neues Thema ein Stück Basiswissen sowas von nicht parat hat, daß er später drüber lachen muß, wenn alles zusammenpaßt.

Äh...im Sinne von "wenn du einen dritten Teiler findest, ist es keine Primzahl". Das ist mathematisch schon korrekt - eine Primzahl hat genau zwei Teiler - aber es ist von der Programmierung her albern, die Existenz von Teilern zu prüfen, von denen man eh weiß, dass es sie gibt (1 lässt sich ja vorher abhandeln), und vor allem verliert man auf die Art die Quadratwurzel-Abkürzung.

Das ist die Art Algorithmus, auf die reine Mathematiker kommen - zwar korrekt, aber unpraktisch. Es ist wie mit dem unendlich großen Hotel, bei dem nach der Beweisführung, dass man immer noch jemanden unterbringen kann, indem man alle anderen verschiebt, niemand mehr darüber nachdenkt, wie man dafür sorgen kann, dass nicht alle Gäste alle fünf Minuten umziehen müssen.

Ansonsten: Frau Merkel ist Physikerin, die macht das empirisch. Wähle zufällig 100.000 Zahlen zwischen 1 und n; je weniger davon n teilen, desto wahrscheinlicher ist n prim. Der BWLer würde im Zweifel im Excel-Handbuch nach einer IST_PRIMZAHL-Funktion suchen.