Primzahlen in C++

13.06.2015, 09:16

AstroNerd

Primzahlen in C++

Hallo Forenuser,
Bei diesem heiteren, fröhlichen und gemütlichen Morgen dachte ich mir, einfach mal zum Spaß ein Programm in C++ schreiben, welches mir Primzahlen ausgibt.
In meinem noch schläfrigen Zustand kam folgender Quelltext raus:

#include<iostream>
using namespace std;
int main(){
int n;
int p;
int a;
cout << "Bis welche Zahl sollen die Primzahlen ausgegeben werden ?" ;
cin >> a;
for(n=1; n=a ; n++)
{
if(for(p=1; p=n; p++){ n/p = n; n/p = 1 ;})
{ cout << n << "\n"; }
}
cin.sync();
cin.get();
return 0;
}

Im Prinzip habe ich hier die Primzahl n definiert, welche jeweils mit p dividiert entweder n oder 1 ergeben soll. Also, für n=1 bis a: wenn für p=1 bis n der Quotient aus n und p immer n oder 1 ergibt, soll n ausgegeben werden. Leider wird mir bei '' if(for(p=1; p=n; p++){ n/p = n; n/p = 1 ;}) '' ein Fehler angezeigt - nun ist mir nicht klar, ob es ein ,,Denkfehler'' oder Syntaxfehler sein soll. Es sei angemerkt, ich bin noch eher Einsteiger in C++.
Mit freundlichem Gruß
AstroNerd
PS.: Bitte keine riesen Alternativquelltexte mit komplizierten Arrays oder langen Syntax empfehlen - aus denen werde ich nicht ganz schlau smile

Jedenfalls noch nicht ...

13.06.2015, 10:15

10001000Nick1

Auf diesen Beitrag antworten »

RE: Primzahlen in C++
Längeren Quellcode bitte in CODE-Tags einschließen (wegen der besseren Lesbarkeit). smile

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:

#include<iostream>
using namespace std;

int main(){
    int n;
    int p;
    int a; 
    cout << "Bis welche Zahl sollen die Primzahlen ausgegeben werden ?" ;
    cin >> a;

    for(n=1; n=a ; n++) 
    {
             if(for(p=1; p=n; p++){ n/p = n; n/p = 1 ;})
             { cout << n << "\n"; }
    } 

    cin.sync();
    cin.get();
    return 0;
}

In C/C++ ist "=" ein Zuweisungsoperator, z.B. wird bei "i=1" der Variablen i der Wert 1 zugewiesen. Wenn du zwei Zahlen auf Gleichheit überprüfen willst, dann musst du "==" benutzen.

Deine for-Schleifen funktionieren so nicht. Syntax einer for-Schleife:

code:
1: 2: 3: 4:	for(Initialisierung; Bedingung; Fortsetzung) { Anweisung(en) }

1. Zuerst wird die Variable initialisiert, d.h. auf einen bestimmten Wert gesetzt.
2. Die Bedingung wird überprüft. Falls falsch, wird die for-Schleife beendet. Falls wahr, dann weiter zu Schritt 3.
3. Die Anweisung(en) wird/werden ausgeführt.
4. Die Anweisung Fortsetzung wird ausgeführt.
5. Weiter zu Schritt 2.

D.h. wenn du schreibst "for(n=1; n=a; n++) { ... }", dann steht bei Bedingung eine Zuweisung (wie der Compiler damit umgeht: siehe Ifindus Beitrag). Aber auch mit "for(n=1; n==a; n++) { ... }" erhältst du nicht das gewünschte Ergebnis: n wird auf den Wert 1 gesetzt und dann überprüft, ob n==a wahr ist, was nicht der Fall sein wird (es sei denn, der User hat den Wert 1 für a eingegeben). Die for-Schleife muss also so aussehen: "for(n=1; n<=a; n++) { ... }".

Das gleiche Problem ist in der for-Schleife in der if-Bedingung; außerdem sind "n/p=n" bzw. "n/p=1" keine Anweisungen, genauso wie "n/p==n" bzw. "n/p==1". Es gibt aber ein noch viel größeres Problem: Eine for-Schleife führt einfach Anweisungen wiederholt aus und wird dann von "if" als wahr betrachtet.

code:
1:	if(Bedingung) {Anweisung}

Die Bedingung wird überprüft; wenn sie wahr ist, wird Anweisung ausgeführt; wenn sie falsch ist, dann nicht.

So, das waren erstmal die Syntax-Fehler. Da gibt es aber noch etwas, was ich nicht verstehe:

Zitat:

Original von AstroNerd
Also, für n=1 bis a: wenn für p=1 bis n der Quotient aus n und p immer n oder 1 ergibt, soll n ausgegeben werden.

Wie kommst du darauf, dass n dann eine Primzahl ist?

13.06.2015, 10:17

IfindU

Auf diesen Beitrag antworten »

RE: Primzahlen in C++
Fangen wir mit den nicht-inhaltlichen Dingen an:
For-Schleifen erhalten als zweites Argument: "Solange wie folgendes gilt". D.h.

code:
1:	for ( n = 0; n < 100; n++)

würde 100-mal aufgerufen werden, jeweils für n = 0, dann n = 1 usw.
Was

code:
1:	for ( n = 0; n = 100; n++)

macht ist eine Endlosschleife: Die Frage "Ist n = 100" ist nämlich in C-Syntax immer wahr. Das einfache Gleichheitszeichen ordnet n nämlich den Wert 100 zu. Jeder Wert ungleich 0 ist wahr, also wird sie immer weiter aufgerufen.
Was du eher meintest ist

code:
1:	for ( n = 0; n == 100; n++)

Das fragt wirklich "Ist denn n das gleiche wie 100". Die For-Schleife liest sich in Worten: Setze n = 0 und schaue nach ob n gleich 100 ist. Wenn ja, führe das in der for-schleife für n = 0 auf und wenn du fertig bist, erhöhe n um 1 (der n++ Befehl). Macht er natürlich nie, weil n nicht gleichzeitig 0 und 100 sein kann.
Was du also wirklich meinst ist mein erster Vorschlag.

Weiter gehts:
Der if Befehl erwartet eine Aussage der Form true or false (er interprertiert Zahlen ungleich 0 als wahr, und die 0 als falsch). Eine for-Schleife ist weder wahr noch falsch.

D.h. besser wäre for (bla) { if (n prim ist) cout << n; }.

Der Compiler wird sich übrigens nicht über inhaltliche Dinge beschweren -- selbst wenn er intelligent genug wäre, so könnte das was du geschrieben hast, genau das sein was du willst.

Ein weiterer Fehler ist n/p = n. Er versucht der temporären Zahl n/p den Wert n zuzordnen. Danach versuchst du ihm den Wert 1 zuzuordnen. Wichtig: Links der Wert wird überschrieben, und zwar mit dem rechten Wert. Falls du vergleichen willst, so musst du es mit == tun.
a == b
liefert wahr, wenn a und b gleich sind und falsch sonst.

Also was du laut Text beschreibst ist

code:
1:	if ( ( n/p == n) \|\| (n/p == 1) )

.
Du musst if nämlich sagen, ob du beides gleichzeitig erfühlt haben willst (z.B. mit "&&") oder wenn er weitermachen soll, sobald auch nur eine davon erfüllt ist (hier mit "||").

Mischung aus C und Mathematik:
n/p in C ist (für postive n,p) das gleiche wie das mathematische $\begin{eqnarray*} \left\lfloor \frac n p \right\rfloor \end{eqnarray*}$ . Er nimmt die Zahl, und rundet dann ab. Dann beschreiben deine Bedingungen einfach keine Primzahlen. Eine ganze Zahl p ist prim, falls $\begin{eqnarray*} \frac p n \not\in \mathbb Z \end{eqnarray*}$ , außer für $\begin{eqnarray*} n = \pm 1 \end{eqnarray*}$ und $\begin{eqnarray*} n = \pm \end{eqnarray*}$ . Das Minus können wir mal getrost streichen. Also willst du nachschauen, ob $\begin{eqnarray*} \frac p n \in \mathbb N \end{eqnarray*}$ für ein n.

Das Programmiertechnisch einfachste wäre also nachzugucken, ob es $\begin{eqnarray*} m,n \in \mathbb N \end{eqnarray*}$ gibt, s.d. $\begin{eqnarray*} p = m \cdot n \end{eqnarray*}$ . Trivialerweise kann m,n < p wählen. Das ist zwar extrem langsam, aber sonst kann man nicht länger nicht-nur mit ints arbeiten (wenigstens ist mir keine Methode bewusst).

13.06.2015, 10:46

AstroNerd

Auf diesen Beitrag antworten »

Ich bedanke mich herzlich bei euch beiden smile

Wenn eine natürliche Zahl $\begin{eqnarray*} n \end{eqnarray*}$ mit einer weiteren natürlichen Zahl $\begin{eqnarray*} p \end{eqnarray*}$ dividiert wird und der Quotient als Ergebnis nur $\begin{eqnarray*} n \end{eqnarray*}$ oder $\begin{eqnarray*} 1 \end{eqnarray*}$ sein kann, so handelt es sich bei $\begin{eqnarray*} n \end{eqnarray*}$ um eine Primzahl. Ich habe meinen Quelltext nun ein wenig überarbeitet. Wäre folgendes nun eher passend ?

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:

#include<iostream>
using namespace std;
int main(){
    int n;
    int p;
    int a;
    cout << "Bis welche Zahl sollen die Primzahlen ausgegeben werden ?" ;
    cin >> a;
    for(n==1; n<=a ; n++) 
    {
             if(for(p==1; p<=n; p++){ n/p == n || n/p == 1 ;})
             { cout << n << "\n"; }
    } 
    cin.sync();
    cin.get();
    return 0;
}

Wenn wir den Quelltext Schritt für Schritt durchgehen. Mit

code:
1: 2: 3: 4: 5:	int n; int p; int a; cout << "Bis welche Zahl sollen die Primzahlen ausgegeben werden ?" ; cin >> a;

wird zunächst definiert, dass $\begin{eqnarray*} n \end{eqnarray*}$ , $\begin{eqnarray*} p \end{eqnarray*}$ und $\begin{eqnarray*} a \end{eqnarray*}$ natürliche Zahlen sind, $\begin{eqnarray*} a \end{eqnarray*}$ wird initialisiert.
Dann:

code:
1:	for(n==1; n<=a ; n++) {

für $\begin{eqnarray*} \sum_{n=1}^a n \end{eqnarray*}$ gilt:

code:
1: 2: 3:	if(for(p==1; p<=n; p++){ n/p == n \|\| n/p == 1 ;}) { cout << n << "\n"; } }

Wenn für $\begin{eqnarray*} p = 1 \end{eqnarray*}$ bis $\begin{eqnarray*} n \end{eqnarray*}$ der Quotient $\begin{eqnarray*} \frac{n}{p} = n \end{eqnarray*}$ oder $\begin{eqnarray*} \frac{n}{p} = 1 \end{eqnarray*}$ gilt, soll $\begin{eqnarray*} n \end{eqnarray*}$ ausgegeben werden.
Das wird dann für das nächste $\begin{eqnarray*} n \end{eqnarray*}$ ausprobiert.
Schaut's nun besser aus ?
Mit freundlichem Gruß
AstroNerd

13.06.2015, 10:53

10001000Nick1

Auf diesen Beitrag antworten »

Da ist immernoch das Problem mit der for-Schleife in der if-Bedingung, die da keinen Sinn macht. Und schau nochmal in meinem Beitrag in die Syntax einer for-Schleife. Da, wo Anweisung(en) steht, stehen bei dir Vergleiche zweier Zahlen. Da meckert der Compiler also wieder rum.

Zitat:

Original von AstroNerd
Wenn eine natürliche Zahl $\begin{eqnarray*} n \end{eqnarray*}$ mit einer weiteren natürlichen Zahl $\begin{eqnarray*} p \end{eqnarray*}$ dividiert wird und der Quotient als Ergebnis nur $\begin{eqnarray*} n \end{eqnarray*}$ oder $\begin{eqnarray*} 1 \end{eqnarray*}$ sein kann, so handelt es sich bei $\begin{eqnarray*} n \end{eqnarray*}$ um eine Primzahl.

Nein. Nimm z.B. $\begin{eqnarray*} n=5, p=2 \end{eqnarray*}$ . In der Ganzzahldivision ist 5/2=2, also nicht 1 oder n; und trotzdem ist 5 eine Primzahl.

13.06.2015, 11:10

AstroNerd

Auf diesen Beitrag antworten »

Wenn das Ergebnis von $\begin{eqnarray*} \frac{n}{p} \end{eqnarray*}$ nur eine natürliche Zahl sein kann und dies gleich $\begin{eqnarray*} n \end{eqnarray*}$ oder $\begin{eqnarray*} 1 \end{eqnarray*}$ ergibt, so handelt es sich bei $\begin{eqnarray*} n \end{eqnarray*}$ um eine Primzahl. Bei $\begin{eqnarray*} n=5 \end{eqnarray*}$ und $\begin{eqnarray*} p = 2 \end{eqnarray*}$ ist also $\begin{eqnarray*} \frac{5}{2} = 2,5 \end{eqnarray*}$ und somit das Ergebnis keine natürliche Zahl. Es soll im Prinzip ausgetestet werden:

Wir nehmen 1. Nun schauen wir, ob für $\begin{eqnarray*} \frac{1}{1} = 1 \end{eqnarray*}$ ist. Wenn ja, wird 1 ausgegeben.
Wir nehmen 2. Nun schauen wir, ob für $\begin{eqnarray*} \frac{2}{1} = 2 \end{eqnarray*}$ , $\begin{eqnarray*} \frac{2}{2} = 1 \end{eqnarray*}$ ist. Wenn ja, wird 2 ausgegeben.
Wir nehmen 3. Nun schauen wir, ob für $\begin{eqnarray*} \frac{3}{1} = 3 \end{eqnarray*}$ , $\begin{eqnarray*} \frac{3}{3} = 1 \end{eqnarray*}$ ist. Wenn ja, wird 3 ausgegeben. $\begin{eqnarray*} \frac{3}{2} \end{eqnarray*}$ wird ignoriert, da das Ergebnis daraus keine natürliche Zahl ist (nämlich $\begin{eqnarray*} 1,5 \end{eqnarray*}$ ).
Wir nehmen 4. Nun schauen wir, ob für $\begin{eqnarray*} \frac{4}{1} = 4 \end{eqnarray*}$ , $\begin{eqnarray*} \frac{4}{2} = 2 \end{eqnarray*}$ und $\begin{eqnarray*} \frac{4}{4} = 1 \end{eqnarray*}$ ist. $\begin{eqnarray*} \frac{4}{3} \end{eqnarray*}$ wird ignoriert, da dies keine natürliche Zahl ist. 4 wird nicht ausgegeben, da $\begin{eqnarray*} \frac{4}{2} = 2 \end{eqnarray*}$ ist und die Bedingung, dass der Quotient nur $\begin{eqnarray*} \frac{n}{p} = n \end{eqnarray*}$ bzw. $\begin{eqnarray*} \frac{n}{p} = 1 \end{eqnarray*}$ sein darf, nicht erfüllt ist
Und wir nehmen alle natürliche Zahlen bis $\begin{eqnarray*} a \end{eqnarray*}$ .
Mit freundlichem Gruß
AstroNerd

13.06.2015, 11:22

10001000Nick1

Auf diesen Beitrag antworten »

Anscheinend weißt du nicht genau, wie die Ganzzahldivision in C++ funktioniert. Schau dir nochmal Ifindus Beitrag an: Wenn du zwei Integers dividierst, ist das Ergebnis wieder ein Integer.

13.06.2015, 11:35

AstroNerd

Auf diesen Beitrag antworten »

Oh oh ...
Wo das Problem liegt habe ich verstanden. Wie ich das aber lösen soll, dass er keine Ganzahldivision sondern allgemeine Division benutzen soll, ist mir nicht bewusst. Soll ich n, p und a evtl. als float oder double deklarieren ?
Mit freundlichem Gruß
AstroNerd

13.06.2015, 12:03

Guppi12

Auf diesen Beitrag antworten »

Das würde dein Problem lösen, ist hier aber nicht der Weg, den man gehen sollte. (Vielleicht gibt es dann auch Probleme mit der Genauigkeit.) Nutze lieber den modulo Operator %. a % b gibt den Rest der Division von a durch b zurück.

Neue Frage »

Antworten »

Primzahlen in C++

Verwandte Themen