Primzahlen ausgeben

ThaRealMatix

Hallo,

ich versuche mich gerade an einem Programm, das alle Primzahlen die kleiner als eine eingegebene Zahl sind ausgeben soll. Also nict deren Anzahl, sondern jede für sich.

Formatierung habe ich noch nicht darin, aber offensichtlich geht nicht mal meine Überlegung.

Folgenden Quelltext habe ich mir zusammengedacht:

#include <iostream>
using namespace std;

int main()
{
	int zahl=0;
	int teiler=2;
	bool isPrime;

	cout << "Bitte geben Sie eine Zahl ein: " << endl; 
	cin >> zahl;

	cout << "Folgende Primzahlen sind kleiner als Ihre eingegebene Zahl: " << endl;

	while (teiler <=zahl)
	{
		int teiler2=0;

		while (teiler2<=teiler)
		{
			if (teiler%teiler2==0 && teiler2!=1 || teiler2!=teiler)
			{
				isPrime = false;
			}
			else
			{
				isPrime = true;
			}
		teiler2++;
		}
		if (isPrime == true)
		{
			cout << teiler2;
		}
		teiler++;
	}

	system("PAUSE");

	return 0;
}

Nun ist die Frage, ob der ganze Quelltext Müll ist, oder ich nur an einer bestimmten Stelle Bockmist gebaut habe

Gruß

Matix

Werner Salomon

ThaRealMatix schrieb:

Nun ist die Frage, ob der ganze Quelltext Müll ist, oder ich nur an einer bestimmten Stelle Bockmist gebaut habe

Hallo Matix,

nun der Code wird in der Zeile 21 mit 'Division by Zero' abstürzen, da am Anfang teiler2 immer =0 ist.

Zurückgefragt: wozu meinst Du zwei Teiler (teiler, teiler2) zu benötigen. Einer würde doch genügen - oder?

Gruß
Werner

Ich denke so wie ich das hier gemacht habe ist es rel. simpel und fast identisch mit deinem Code.

#include <iostream>

void main(void)
{
    int a,b,c;

    std::cout<<"Primzahlen unter 100:";

	while(a<=100)
	{
                c=0;

                for(b=1; b<=100; b++)
                {
                        if(!(a%b))
                        {
                                c++;
                        }
                }

                if(c==2)
                {
                        std::cout<<std::endl<<a;
                }

                a++;
	}

	std::cin.get(); //Schliessen der Konsole verhindern
}

Konrad Rudolph

Hi El C,

'main' hat immer Rückgabewert 'int'. 'void' ist falsch.

Wofür stehen 'a', 'b' und 'c'? Wären da nicht andere Namen angebracht, die ihre Aufgabe beschreiben? Außerdem sollte man Variablen erst dort deklarieren, wo man sie auch braucht, nicht alle am Anfang der Funktion.

ThaRealMatix

Hallo,

ich dachte, dass ich zwei Teiler brauche, weil der erste ja die potentielle Primzahl ist, der zweite soll nun eben überprüfen, ob es sich bei dieser Zahl auch um eine handelt, wozu ich eben meine Funktion benutzen wollte. Der erste soll also die potentielle Primzahl sein, der zweite teilt nun und überprüft, ob es überhaupt eine ist.

Es mag ja sein das der Code im zweiten Text mein Problem löst, er hilft mir nur leider absolut nicht die Logik zu verstehen, es wäre also schön, wenn man mir anhand meines Quelltextes sagen könnte, wo ich die Fehler mache, und vielleicht bei der Korrektur sagt wieso es so sein muss, ansonsten ist der Lerneffekt nämlich = 0

Wenn man dem Link folgt sieht man, dass ich das ursprünglich in C codiert habe und da werden Variablen halt am Anfang deklariert und void ist gültig als Rückgabetyp von main.
Intelligentere Namen für die Variablen wären sicher gut, das stimmt.

Ich habe jetzt noch kurz in einem Buch nach gesehen; void main(void) scheint durchaus gültig zu sein?

ThaRealMatix

Ich will nicht unhöflich sein, aber könntet ihr Eure Grundsatzdiskussion darüber, wie man was warum bennenen sollte und ob man nun dieses oder jenes benutzen darf vielleicht in einem Thread klären, der nichts damit zu tun hat das ich versuche diese Logik zu verstehen?

Ich meine das echt nicht böse, aber ich suche hier Hilfe um das ganze zu lernen und den Sinn dahinter zu verstehen und keine Programmierphilosophie oder ein fertiges Programm dessen Funtkionsweise mir völlig unklar ist, dann hätte ich Google bemüht und wäre sicherlich fündig geworden.

Mein Code ist vielleicht scheisse, ich bin Anfänger, aber ich verstehe ihn wenigstens weil die Logik dahinter, sei sie auch noch so falsch, meinem Geist entsprungen ist.

Ich suche hier wirklich Hilfe und bin auch um jede Hilfe von Euch überaus dankbar, aber wer nicht unmittelbar dazu etwas sagen möchte und mir meine Fehler und/oder falsche Denkweise erläutern kann und will der möge sich doch bitte in einem anderem Posting Klugscheissend verlustieren?

Danke

Konrad Rudolph

ThaRealMatix schrieb:

Ich will nicht unhöflich sein, aber könntet ihr Eure Grundsatzdiskussion darüber, wie man was warum bennenen sollte und ob man nun dieses oder jenes benutzen darf vielleicht in einem Thread klären, der nichts damit zu tun hat das ich versuche diese Logik zu verstehen?

So ist das nunmal in Foren – Diskussionen verzweigen sich. Wenn man das abstellt, dann kann man das Forum auch gleich einmotten.

MOV Weltall,Abfall schrieb:

Ich habe jetzt noch kurz in einem Buch nach gesehen; void main(void) scheint durchaus gültig zu sein?

Wenn das wirklich in dem Buch steht (kann durchaus sein), dann ist das Buch Schrott. Und 'void main' war auch in C noch nie legaler Code.

So, zurück zum Originalproblem:

Ich muss leider zugeben, dass ich hier nicht wirklich Hilfe leisten kann, denn ich verstehe die Logik dahinter nicht. Wozu brauchst Du den zweiten Teiler? Versuch doch mal, die Logik in Worte zu fassen, oder noch besser: in verständlichen Pseudocode. Und dann schau Dir am besten mal das einfachste Verfahren zum Ermitteln der Primzahlen an, das Sieb des Eratosthenes, das Du wahrscheinlich auch versuchst hast, irgendwie zu implementieren.

unskilled

Also ich würde an deiner Stelle schon mal nur die ungeraden Zahlen überprüfen lassen...
Den Rest der Fragen hab ich ma versucht im Quelltext an der passende Stelle zu stellen ^^

while (teiler <= zahl)
    { 
        int teiler2 = 0; //warum initialierst du nen Teiler mit 0? (nimm doch 2 oder, wenn du wirklich nur die ungeraden Zahlen überprüfst, nimm 3)
        while (teiler2<=teiler) //versteh ich au ne so recht -.-
        { 
            if (teiler%teiler2==0 && teiler2!=1 || teiler2!=teiler) 
            { 
                isPrime = false;
            } 
            else 
            { 
                isPrime = true; //vll noch nen break oder so? Ich hab zwar immer noch nicht ganz genau verstanden, was du hier genau machen willst, aber ist es normalerweise nicht so, dass es nachdem du hier weist: 'ah - is ne Primzahl' noch weiter suchst, ob es ne Primzahl ist (ohne diese iwie auszugeben oder nen Zähler zu erhöhen, dass er ne Primzahl gefunden hat ^^)
            } 
        teiler2++; 
        } //while (teiler2<=teiler)
        if (isPrime == true) 
        { 
            cout << teiler2; //hier wäre nen Leerzeichen und/oder nen endl am Ende auch noch sehr gut ^^ sonst haste dann so ne Zeile: '2357...' is ne wirklich schön, oder? ^^
        } 
        teiler++; 
    } //while (teiler <= zahl)

Naja - ich hoffe, es bringt dir bisschen was... Wenn du die Logik dahinter jz mal richtig erklären könntest, dann könnt ich dir evtl au bissl was tolleres, als nur Fragen stellen ^^

ThaRealMatix

Gut... Pseudocode ist der:

Eine Zahl wird eingelesen
Solange der Teiler kleiner oder gleich der Zahl ist soll er ebenso hochgezählt werden

Wenn der Teiler nur durch sich selbst und 1 teilbar ist - und keinen Rest gibt - soll isPrime auf true gesetzt werden, anderfalls auf false

(An dieser Stelle, so meine Überlegung, ist es in C++ nicht wirklich realiserbar und ich muss das gegenteil überprüfen. Also ob der Teiler keinen Rest enthält und wenn das der fall ist, ob er nun nicht 1 und nicht er selber ist. ist das der fall ist er keine Primzahl)

Ist isPrime wahr, soll der Teiler als Primzahl ausgegeben werden, ist isPrimae false soll nicht ausgegeben werden.

Hm... ich sehe gerade, das ich wirklich keinen 2ten Teiler brauche -.-. Aber... wenn ich

teiler%teiler

benutzen würde wäre das Ergebnis ja IMMER 0.

Ich habe den Code mal folgendermaßen abgeändert:

int main()
{
	int zahl=0;
	int teiler=2;
	bool isPrime;

	cout << "Bitte geben Sie eine Zahl ein: " << endl; 
	cin >> zahl;

	while (teiler <=zahl) //check teiler gegen zahl
	{
		if (zahl%teiler ==0) //check Bedingung für Primzahl
		{
			isPrime = false;
			//cout << "false" << teiler2 << endl;
		}
		else
		{
			isPrime = true;
			// cout << "true" << teiler2 << endl;
		}

		if (isPrime == true)
		{
			cout << teiler << " ";
		}
		teiler++; // hochzählen Teiler
	}

	system("PAUSE");

	return 0;
}

Ich weiss nur absolut keinen Weg, zu überprüfen, ob der Teiler nun wirklich nur durch sich selbst und 1 teilbar ist -.- zum kotzen

Konrad Rudolph

Hallo,

Du wirst auf jeden Fall zwei Schleifen brauchen, wenn Du alle Primzahlen ausgeben willst. Ich würde Dir außerdem raten, das Überprüfen auf eine Primzahl in eine Extrafunktion auszulagern, sonst gerät man ja vollkommen durcheinander.

Deine Überlegung dazu war schon ganz gut: um zu überprüfen, ob eine Zahl eine Primzahl ist, zählt man einen andere Zahl hoch und testet, ob die erste Zahl durch die zweite teilbar ist. Wenn dies der Fall ist, dann war die andere Zahl eben keine Primzahl:

bool is_prime(int number) {
    // Jede Zahl ist durch 1 teilbar, deswegen fangen wir bei 2 an.
    for (int test = 2; text < number; ++text)
        // Testen, ob 'number' durch 'test' restlos teilbar ist:
        if (number % test == 0)
            return false;

    // 'number' hat keine Teiler:
    return true;
}

Da kann man jetzt jede Menge optimieren – muss man aber erst mal nicht. Diese Funktion kann man jetzt, wie sie ist, aus der 'main'-Funktion aufrufen und für jede Zahl prüfen, ob diese prim ist (und sie dann ausgeben).

[code]#include <iostream>

int main(){
    int num;
    std::cout << "Zahl: ";
    if( std::cin >> num && num > 1 ){    // 0 und 1 sind weder prim noch zusammengesetzt 
        for( int prime = 2; prime <= num; prime++ )
             if(!( prime % 2 == 0 || prime % 3 == 0 || prime % 5 == 0|| prime % 7 == 0 ))
                   std::cout << prime << char(32);
    }
    std::cin.sync();
    std::cin.get();
    return 0;
}

[/code]

Ist nicht sauber, da 2, 3, 5 und 7 (Primzahlen) nicht angezeigt werden aber ein ein bisschen basteln sollst du ja auch.

unskilled

Gut...

int i = 2; //für i == 1 brauchen wir ja nicht zu testen...
bool isPrime = true; //prizipiell wird davon ausgegangen, dass wir eine Primzahl haben
while ((i < zahl/2) && (isPrime)) //so lange testen, bis fest steht, dass es keine Primzahl ist und i kleiner, als die hälfte der Zahl ist - das könnte man auch noch optimieren, dass er nicht für jeden Durchlauf wieder zahl/2 rechnen muss etc - aber das macht wohl erst bei sehr großen Zahlen nen Unterschied - und überhaupt... ^^
	{
		if (zahl%i == 0) // -> i * n == zahl ==> lt. Def. keine Primzahl mehr (weil i ja hier niemals 1 oder die Zahl an sich sein kann)
			isPrime = false;
		else
			++i; //alternativ auch i++ - ist hier egal, aber ich finde, man sollte sich das von Anfang an angewöhnen, so wenig wie möglich x++ zu nehmen...
	}

Das würde ich an deiner Stelle für das Testen auf eine Primzahl nehmen...
Habs auch bissl kommentiert - hoffe, es ist ausreichend und entspricht deinen Vorstellungen ^^
Deine erste Variante fand ich bissl komisch - sonst hätt ich sie genommen und verändert, aber naja :S

bb ^^

ThaRealMatix

Hm...

also das ganze von unskilled kommt der geforderten Lösung die ich raushaben "soll" am nähesten, ist mir aber total unschlüssig. Wieso eigentlich zahl/2 und wieso ist es keine Primzahl wenn die zahl durch i geteilt keinen Rest hat? normalerweise müsste es doch gerade dann eine potentielle Primzahl sein, weil eine Primzahl ja ohne Rest teilbar sein muss?

Bei meinem Code komme ich nicht weiter, ich bekomme einfach die Unterscheidung nicht hin ob es sich dabei wirklich um eine Zahl handelt die nur durch sich selbst (und 1) teilbar ist -.-

#include <iostream>
using namespace std;

int main()
{
	int zahl=0;
	int teiler=2;
	bool isPrime;

	cout << "Bitte geben Sie eine Zahl ein: " << endl; 
	cin >> zahl;

	while (teiler <=zahl) //check teiler gegen zahl
	{
		for (int test = 2; test < teiler; test++)

        if (teiler % test == 0)
            isPrime = false;

    	else
		{
			isPrime = true;
		}

		if (isPrime == true)
		{
			cout << teiler << " ";
		}
		teiler++; // hochzählen Teiler
	}

	system("PAUSE");

	return 0;
}

Ich weiss du willst Kommentare und Verbesserungsvorschläge zu DEINER Lösung (Das hast du ja schon deutlich gesagt.), aber mach dir doch trozdem mal die Mühe den untenstehenden Code nachzufolziehen.
Der ist doch echt selbsterklärend und einfach.-Du testest einfach jede Zahl einzeln durch, was ist da noch unklar?

#include <iostream>

int main(void)
{
	std::cout<<"Grenzwert: ";
	int grenzwert;
	std::cin>>grenzwert; fflush(stdin);

	//Jede Ganzzahl zwischen 2 und dem benutzerdefinierten Grenzwert koennte eine Primzahl sein,
	//weshalb in der Folge jede durchgetestet wird.
	for(int potenzielle_primzahl=2;potenzielle_primzahl<=grenzwert;potenzielle_primzahl++)
	{
		bool ist_primzahl=true;

		//Ist die potenzielle Primzahl auch durch eine andere Zahl als 1 und sich selbst teilbar?
		for(int teiler=2;teiler<=9;teiler++)
		{
			if(potenzielle_primzahl%teiler==0&&potenzielle_primzahl!=teiler)
				ist_primzahl=false;
		}

		if(ist_primzahl==true)
			std::cout<<potenzielle_primzahl<<std::endl;
	}

	std::cin.get();
	return 0;
}

Wozu ist denn der Quark mit dem Bool gut?
Und warum 2 Schleifen ?

Der Code den ich dir angeboten hab hat nur eine Schleife und 2 Variablen und keine unbekannten Funktionen (like fflush)

Nochmal vereinacht:

#include <iostream>

using namespace std;

int main(){
    int num;
    cout << "Zahl: ";
    if( cin >> num && num > 1 ){    // 0 und 1 sind Sonderfälle, daher nur Zahlen > 1 zulassen
        for( int prime = 2; prime <= num; prime++ )   // von 2 zur eingegeben Zahl alle überprüfen 
             if(!( prime % 2 == 0 || prime % 3 == 0 || prime % 5 == 0|| prime % 7 == 0 ))  
                   // es reicht die Zahl durch 2, 3, 5 und 7 zu teilen 
                   cout << prime << " ";
    }
    cout << endl;
    system("PAUSE");   
    return 0;
}

ThaRealMatix

Hm

ich hab nun folgenden Code

#include <iostream>
using namespace std;

int main()
{
	int zahl=0;

	cout << "Bitte geben Sie eine Zahl ein: " << endl; 
	cin >> zahl;

	for (int teiler=2; teiler<=zahl; teiler++)
	{
		bool isPrime = true;

		for (int teiler2=2; teiler2<=9; teiler2++)
		{
			if (teiler/teiler2==0 && teiler!=teiler2)
			{
				isPrime = false;
			}
		}

		if (isPrime == true)
		{
			cout << teiler << " ";
		}
	}

	system("PAUSE");

	return 0;
}

Der Unterschlägt mir aber zum einen Alle Zahlen von 1-9 und gibt mir zweitens auch die zwölf aus, wenn ich als Zielzahl die 12 wähle ... es ist zum heulen

fflush(stdin) löscht den Eingabebuffer und somit das Enter welches von std::cin dort übrigbleibt.-Das macht dann std::cin.get() Probleme.
Ich wollte nicht system("PAUSE") verwenden, weil ich mir nicht so sicher bin, ob das auch unter Linux hinhaut, denn PAUSE ist ja ein DOS-Befehl.

Ausserdem: Gehört system(const char *command) eigentlich nicht zum C-Header stdlib?-Ein #include <cstdlib> täte evtl. ganz gut für den Stil, oder nicht?

@ThaRealMatix: Du dividierst einfach anstelle einer Modulodivision.