Primzahlen mit Programm ermitteln

B

Bertelcraft

Mitglied
Hallo!
Ich habe mir ein kleines Programm geschrieben, mit dem ich Primzahlen berechnen will.
Leider gibt die Konsole immer vollkommen "irre" Werte aus. Kann mir wer sagen warum?
Code: 
#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{
    int Zahl = 10;
    int Ergebnis;
    int Rechner = 1; 
    
    cout << "Primzahlen" << endl;
    
    for(int Zaehler = 2;Zaehler < Zahl; Zaehler++) //Hier soll jede Zahl vor der maximal Zahl durchgegangen werden
    {
            for(int a = 0; Rechner < Zaehler; Rechner++) //Hier wird die Zahl, die in der Variable Zähler steht, durch alle Zahlen davor dividiert, 
                                                         //ob der Rest 0 ist. Wenn der Rest 0 ist, ist es keine Primzahl, sonst wäre sie ja eine.
            {
            Ergebnis = Zaehler%Rechner;
            if(Ergebnis != 0)
            {
              
                        cout << Ergebnis << endl;
            }
            else
            {}
            
            }
            Rechner = 1; //Hier wird der Rechner wieder auf 1 zurück gesetzt, dass wieder alle Zahlen vor Zaehler durchlaufen werden können.
    }
    system("PAUSE");
    return EXIT_SUCCESS;
}
 
Hi.

Dein Algorithmus ist falsch. Um zu testen ob eine Zahl n eine Primzahl ist, mußt du (trivialer Weise) für alle Zahlen von 2 bis (n -1) testen ob eine von diesen Teiler der Zahl n ist.

Nur wenn keine Zahl gefunden werden konnte, dann ist die Zahl eine Primzahl.

Du läßt aber jede Zahl als Primzahl durchgehen, für die du eine Zahl findest, die kein Teiler ist von n.

Außerdem läßt du dir den Rest der Ganzzahldivision ausgeben. Vermutlich möchtest du die Primzahl ausgeben wenn du eine gefunden hast.

Schreib dir am besten erstmal eine Funktion, die dir berechnet ob eine einzelne Zahl eine Primzahl ist. Diese Funktion kannst du dann später in eine Schleife einbauen.

Gruß
 
Zuletzt bearbeitet:
Ein Tipp noch: Es reicht aus von 2 bis n/2 zu testen, da ein Teiler größer als n/2 nie eine ganze Zahl ergeben kann.

Gruß,
derPfaff
 
Ich komm einfach nicht drauf. Ich hab den Code jetzt umgeschrieben, aber er geht immer noch nicht so wie ich wollte.

Das ist die main()-Funktion:
Code: 
int main(int argc, char *argv[])
{
    int n = 10;
        bool Primzahl;
    int Ergebnis;
    for(int z = 1; z<n-1; z++)
    {
            Ergebnis = Rechner(n, Primzahl);
            if(Primzahl = true)
            { cout << n << endl;}
            else
            {}
    }
    
    system("PAUSE");
    return EXIT_SUCCESS;
}
und das ist die Berechnung für die Primzahl:
Code: 
int Rechner(int n, bool Primzahl)
{

    for(int i = 2; i==n-1; ++i)
    {
            
            if(n%i == 0)
            {
                        Primzahl = true;
                        
            }
            else
            {
                        if(Primzahl != false)
                        { Primzahl = false; }
                        else
                        {}
            }
    }
    return Primzahl;

}
Ich finden den Fehler nicht. Ich habe wohl einen kleinen Denkfehler. ;)
 
Hi.

Es scheint jetzt bist du völlig raus.

Du hast die Funktion zu kompliziert gemacht.

Die Funktion sollte folgende Signatur haben:
C++: 
bool primzahl(int x);
Wenn du innerhalb der Funktion in der Schleife einen Teiler findest, kannst du sofort false zurückgeben. Wurde die Schleife in der Funktion komplett abgearbeitet - also es wurde kein Teiler gefunden - dann gibst du true zurück.

Du verwendest gar nicht den Rückgabewert der Funktion. So sollte es innerhalb der Schleife aussehen:
C++: 
if (primzahl(z)) {
  cout << z << endl;
}
Gruß
 
Okay, ich recycle mal diesen älteren Thread: Hallo erstmal.

Ich habe grade vor zwei Tagen angefangen, mich mit C++ zu beschäftigen und habe als Fingerübung auch mal ein Primzahl-Programm versucht:

Code: 
int main()
{
	int zahl, teiler, max;
	bool prim;
	cout << "Primzahlen berechnen bis zu: ";
	cin >> max;
	cout << "\n";
	for(zahl = 2; zahl <= max; zahl++)
	{
		prim = true;
		for(teiler = 2; teiler < zahl; teiler++)
		{
			if(zahl % teiler == 0)
			{
				prim = false;
			}
		}
		if(prim == true) {
			cout << zahl << " ";
		}
	}
	cout << "\n" << endl;
	system("PAUSE");
        return EXIT_SUCCESS;
}

Das ganze funktioniert super, die Lösung kommt mir allerdings ein wenig unelegant vor.
Deswegen mal meine Frage an die Cracks hier: Gibt es eine elegantere Lösung und wenn ja, wie sieht die aus?
 
Hallo,
Nogg hat gesagt.:
Das ganze funktioniert super, die Lösung kommt mir allerdings ein wenig unelegant vor.
Deswegen mal meine Frage an die Cracks hier: Gibt es eine elegantere Lösung und wenn ja, wie sieht die aus?
Zum Vergrößern anklicken....

ja gibt es. Es ist ja so das wenn du eine Zahl überprüfst ob sie sich durch einen Teiler teilen lässt, den entgegengesetzten Teiler auch gleich mit prüfst. Bspw. Wenn 15 durch 3 teilbar ist, ist 15 auch durch 5 teilbar. Du erreichst den "entgegengesetzten" Teiler nach der Wurzel der Zahl. D.h. also das deine innere Schleife nur bis zur Wurzel der Zahl prüfen muss:

C: 
for(zahl = 2; zahl <= max; zahl++)
{
  int maxTeiler;
  maxTeiler = = ((int) sqrt(zahl));
  prim = true;
  for(teiler = 2; teiler < maxTeiler; teiler++)
  {
...

Um noch ein bisschen Optimierung rauszuholen kannst du auch mit dem Produkt rechnen:

C: 
int teiler = 2;
...
for(zahl = 2; zahl <= max; zahl++)
{
  int sqrTeiler;
  sqrTeiler = teiler * teiler;
  for(teiler = 2; sqrTeiler < zahl; teiler++)
  {
...

Welche von beiden Varianten jetzt schneller ist ist schwer zu sagen, jedoch schon um einiges schneller als die Variante in der der Teiler immer bis == zahl überprüft werden muss.

btw seh grad noch: Desweiteren kannst du innerhalb von

C: 
if(zahl % teiler == 0)
{
  prim = false;
  break;
}
ein break einführen, sodass er aus der inneren Schleife rausspringt sobald es keine Primzahl mehr sein kann.


Gruß,
RedWing
 
Zuletzt bearbeitet:
Hallo,

RedWing hat gesagt.:
btw seh grad noch: Desweiteren kannst du innerhalb von

C: 
if(zahl % teiler == 0)
{
  prim = false;
  break;
}
ein break einführen, sodass er aus der inneren Schleife rausspringt sobald es keine Primzahl mehr sein kann.
Zum Vergrößern anklicken....
Stimmt, das ist mir auch grade noch aufgefallen. :-(
Danke, diese Änderung bringt natürlich eine ganz erhebliche Performance-Steigerung.

Im Grunde wollte ich aber eher darauf hinaus, ob die Lösung mittes der prim-Variable in meinem Beispiel in Ordnung ist, oder ob es da bessere Lösungen gäbe (mal unabhängig davon, ob eine solche Lösung performanter wäre; letztlich will ich ja kein praxisorientiertes Programm, sondern das ganze sollte nur eine persönliche Übung sein.)
Ich habe es ja so gelöst, dass die rabiable initial auf 1 gesetzt wird und dann bei einem Schleifenaufruf auf 0 gesetzt wird, wenn es keinen Rest gibt.
Wenn ich 5 überprüfe, will ich ja wissen, ob bei derTeilung durch 2 oder 3 oder 4 kein Rest bleibt. Die Lösung mit der prim-Variable kommt mir (intuitiv) ein wenig umständlich vor. Gibt es eventuell eine [bessere] Möglichkeit, das z. B. in einen Ausdruck zu verpacken?

C: 
prim = true;
		for(teiler = 2; teiler < zahl; teiler++)
		{
			if(zahl % teiler == 0)
			{
				prim = false;
Danke erstmal schon für die Antwort soweit.
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück