Hallo Limonade,
Es gibt eine Sache, die beim Erstellen von Programmen essentiell ist:
divide et impera
Heißt 'Teile und Herrsche', heißt beim Programmieren: zerlege das Problem in möglichst kleine Einheiten und zwar derart, dass diese möglichst wenig miteinander zu tun haben. mathe53 hat dies in seiner Antwort schon gezeigt, in dem er den Algorithmus zur Primzahlprüfung in eine Funktion Ist_Primzahl verpackt hat. Das nennt man übrigens 'Kaspelung'.
Dieses Prinzip ist deshalb so wichtig, da man bei mittleren bis größeren Programmen ansonsten völlig den Überblick verlieren würde, und am Ende nur noch Chaos produziert. Und bei kleinen Programmen kann man das schon mal üben ..
Eine Konsequenz dieses Prinzip ist es auch, auf globale Variablen möglichst zu verzichten. Die Variablen oberhalb von 'int main {' sollten und brauchen da gar nicht stehen!
Weiter: bennen die Variablen und auch alles andere sinnvoll. Also nicht 'a' oder 'b', sondern besser 'fib_i_minus_1' und 'fib_i' für die Fibonaccizahlen \(f_{i-1}\) und \(f_i\).
Kommen wir mal zur Kapselung der Fibonaccizahlen. Das ist ein schönes Beispiel für eine kleine Klasse. Um eine Fibonaccizahl zu berechnen benötigt man zwei auf einander folgende. In einer Klasse sähe das so aus:
class Fibo {
private:
int m_fib_i;
int m_fib_i_minus_1;
};
Das 'm_' steht für Member, und das 'm_fib_i' ist die i'te Fibonaccizahl \(f_i\) sowie der Vorgänger 'm_fib_i_minus_1' \(f_{i-1}\). Und die sind 'private', weil sie sollten von außerhalb nicht verändert werden. Wir möchten natürlich die aktuelle Zahl haben, also braucht man noch ein 'get':
class Fibo
{
public:
int get() const {
return m_fib_i;
}
private:
int m_fib_i;
int m_fib_i_minus_1;
};
Jetzt wollen wir natürlich auch zur nächsten Fibonaccizahl übergehen, dazu implementiere ich eine Funktion 'next'
class Fibo
{
public:
int get() const {
return m_fib_i;
}
void next() {
int fib_i_plus_1 = m_fib_i + m_fib_i_minus_1;
m_fib_i_minus_1 = m_fib_i;
m_fib_i = fib_i_plus_1;
}
private:
int m_fib_i;
int m_fib_i_minus_1;
};
Oben siehst Du die bekannte Gleichung \(f_{i+1} = f_i+ f_{i-1}\). Anschließend geschieht der Übergang von \(i\) nach \(i+1\). Das aktuelle \(i\) ist um \(1\) erhöht.
Am Anfang - nach Erstellen eines Objekts der Klasse 'Fibo' - soll \(i=0\) sein und das 'get()' natürlich eine \(f_0=0\) liefern. Das \(f_{(-1)}\) berechnet sich aus$$f_1 = f_0 + f_{(-1)} \implies f_{(-1)} = f_1 - f_0 = 1-0=1$$und damit ist klar, wie die Member der Klasse initialisiert werden müssen. Im folgenden gleich das ganze Programm:
#include <iostream>
class Fibo
{
public:
Fibo()
: m_fib_i(0) // f_0 = 0
, m_fib_i_minus_1(1) // f_(-1) = 1
{}
int get() const {
return m_fib_i;
}
void next() {
int fib_i_plus_1 = m_fib_i + m_fib_i_minus_1;
m_fib_i_minus_1 = m_fib_i;
m_fib_i = fib_i_plus_1;
}
private:
int m_fib_i;
int m_fib_i_minus_1;
};
int main() {
using namespace std;
for(int m; cout << "Type in a number: ", cin >> m; ) {
cout << "Fibonacci numbers up to " << m << endl;
for(Fibo f; f.get() <= m; f.next() ) {
cout << f.get() << " ";
}
cout << "\n" << endl;
}
return 0;
}
Dieses Programm gibt alle Fibonaccizahlen bis zu einer Obergrenze 'm' aus. Und nun sollte es kein Problem sein, den Primzahltest von mathe53 hinzu zu fügen. Das erweiterte 'main' sähe so aus:
int main() {
using namespace std;
for(int m; cout << "Type in a number: ", cin >> m; ) {
cout << "Fibonacci primes up to " << m << endl;
for(Fibo f; f.get() <= m; f.next() ) {
if(Ist_Primzahl(f.get())) { // ist es eine Primzahl?
cout << f.get() << " "; // ... nur dann ausgeben
}
}
cout << "\n" << endl;
}
return 0;
}
Bem.: 'Ist_Primzahl' von mathe53 enthält einen kleinen Fehler. Oben muss es 'aZahl < 2' statt 'aZahl <= 2' heißen. Die 2 ist auch eine Primzahl!
Da Du das std::sqrt nicht nutzen darfst (so ein Quatsch!), schnitze Dir ein eigenes.
namespace limonade { // namespace != std, um Verwechslungen zu verhindern
double abs_(double a) {
if( a < 0)
return -a;
return a;
}
int sqrt(int a) {
assert(a >= 0); // Eingangsbedingung prüfen
if( a < 2 )
return a;
double x_prev;
double x = a/2.; // 1. Schätzung
do {
x_prev = x; // bisheriges x merken
x = (x_prev + a/x_prev)/2;
} while( abs_(x_prev - x) > 0.5 );
return int(x);
}
}
und füge es so in die Funktion Ist_Primzahl ein
bool Ist_Primzahl( int zahl ) {
if ( zahl < 2) {
return false; // Primzahlen beginnen erst mit 2
}
int max_teiler = limonade::sqrt(zahl);
for ( int teiler=2; teiler <= max_teiler; ++teiler) {
if( zahl % teiler == 0) {
return false; // keine Primzahl; 'teiler' ist Teiler von 'zahl'
}
}
return true; // Primzahl
}
falls Du noch Fragen hast, nur heraus damit ;-)
Gruß Werner
