✔ C++ Primzahl problem

M

muntir

Grünschnabel

hallo ich hab die aufgabe bekommen ein c++ programm erklären zu können habe jedoch ein problem an dem ich nicht weiter komme und hoffe ihr könnt mir weiterhelfen :)
C++: 
int Zahl1;
int Zahl2;
int Zahl3;
int Zahl4;
int Auforderung;

float x;
float Berechnung1;
float Berechnung2;
float Berechnung3;
float Berechnung4;
float Untergrenze;
float Obergrenze;
Programm1:

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

Berechnung1 = x / 2;
Zahl1 = x/2;

Berechnung2 = x / 3;
Zahl2 = x / 3;

Berechnung3 = x / 5;
Zahl3 = x / 5;

Berechnung4 = x / 7;
Zahl4 = x / 7;

if (x == 2 or x == 3 or x == 5 or x == 7)
{
cout << "Ihre Zahl " << x << " ist eine Primzahl" << endl;
}
else
if (Berechnung1 == Zahl1)
{
cout << "Ihre Zahl " << x << " ist keine Primzahl" << endl;
}
else
if (Berechnung2 == Zahl2)
{
cout << "Ihre Zahl " << x << " ist keine Primzahl" << endl;
}
else
if (Berechnung3 == Zahl3)
{
cout << "Ihre Zahl " << x << " ist keine Primzahl" << endl;
}
else
if (Berechnung4 == Zahl4)
{
cout << "Ihre Zahl " << x << " ist keine Primzahl" << endl;
}
else
cout << "Ihre Zahl " << x << " ist eine Primzahl" << endl;
meine frage ist was machen die berechnung genau ich weiß das int keine kommerstellen anzeigt und float schon. trz verstehe ich den zusammenhang der rechnung und der dannachfolgige if befehel

if (x == 2 or x == 3 or x == 5 or x == 7) { cout << "Ihre Zahl " << x << " ist eine Primzahl" << endl;

ist mir auch unklar wieso x diese zahl sein muss um eine primzahl zu sein 17 ist zB auch eine primzahl und steht dort nicht drinne.

ich hoffe ich hab mich nicht zu unklar ausgedrückt und hoffe das ihr mir weiter helfen könnt :)
 
Zuletzt bearbeitet von einem Moderator:
Hallo und willkommen!

muntir hat gesagt.:
hallo ich hab die aufgabe bekommen ein c++ programm erklären zu können habe jedoch ein problem an dem ich nicht weiter komme und hoffe ihr könnt mir weiterhelfen :)
Zum Vergrößern anklicken....
Darf man nach dem Kontext fragen? Soll stilistisch (und/oder syntaktisch) oder logisch (semantisch) geprüft werden?

muntir hat gesagt.:
if (x == 2 or x == 3 or x == 5 or x == 7)
Zum Vergrößern anklicken....
Ist das C++? Korrekt würde das
C++: 
if(x ==2 || x ==3 || x ==5 || x ==7)
lauten - es stellt sich mir die Frage, woher du diesen Code hast. Z.B. wird auch "Aufforderung" nicht verwendet, die Werte sollten initialisiert werden und die Divisionen würden mit korrekter Bezeichnung auch besser funktionieren (z.B. "/ 2.0f" statt "/ 2").

muntir hat gesagt.:
ich weiß das int keine kommerstellen anzeigt und float schon
Zum Vergrößern anklicken....
Das stimmt nur halb. Anzeigen tut es ohnehin ein Konverter, der Mensch liest nicht so gerne binär - der Computer hingegen schon. Das führt z.B. dazu, dass float ungenau ist - alle Werte, die sich nicht durch 2^(-x) darstellen lassen, stimmen ab einer bestimmten Nachkommastelle nicht mehr. Int ist dafür nur dann für Divisionen geeignet, wenn der Dividend ein Vielfaches des Divisors ist - ansonsten wird abgerundet (z.B. 3/2==1).

Daher sind auch die Vergleiche wie "if(Berechnung1 == Zahl1)" ziemlich mutig und der Compiler wird zumindest eine Warnung auswerfen.
muntir hat gesagt.:
trz verstehe ich den zusammenhang der rechnung und der dannachfolgige if befehel
Zum Vergrößern anklicken....


Das Konzept des Programmes ist folgendes:
Vorgaben:
- Wir prüfen anhand einer Primzahl p.
- Die zu prüfende Zahl sei n.

Schritte:
1. F := n/p, wobei F das "exakte" Resultat ist (Berechnung1 = x /2)
2. N := n/p, wobei N das abgerundete Resultat ist (Zahl1 = x/2)
3. Ist F gleich N?

Da für jede ganze Zahl b gilt: b = a * x, wobei a und x ebenfalls Ganzzahlen sind (=man kann jede Zahl faktorisieren, zumindest mit sich selbst und 1), ist, auf dieses Beispiel angewandt n = N * p nur dann der Fall, wenn sich n zerlegen lässt - was für Primzahlen eben nicht zutrifft, wenn man 1 für N und p ausschliesst (1 ist keine Primzahl).

Teilen kann man ja dennoch - und da kommt die Kommazahl ins Spiel: Wenn die exakte Division ein anderes Resultat ergibt als die abgerundete, dann ist die Zahl nicht (ganzzahlig) teilbar und somit möglicherweise prim - man muss diesen Test für alle p < n wiederholen.

Allerdings: Protip:
Dasselbe in besser(TM) erreicht man mit Modulo: Eine Zahl ist nicht prim, wenn gilt: n mod p = 0. Oder in C++ if(n % p == 0) std::cout << "Zahl nicht prim";.

muntir hat gesagt.:
ist mir auch unklar wieso x diese zahl sein muss um eine primzahl zu sein 17 ist zB auch eine primzahl und steht dort nicht drinne.
Zum Vergrößern anklicken....
Stimmt. Daher hat es das letzte else: Wenn x nicht 2, 3, 5 oder 7 ist und sich nicht teilen lässt (durch die 4 ziemlich zufälligen Anwendungen des Algorithmus oben ermittelt), ist sie auch prim.

muntir hat gesagt.:
ich hoffe ich hab mich nicht zu unklar ausgedrückt und hoffe das ihr mir weiter helfen könnt :)
Zum Vergrößern anklicken....
Naja. Um ehrlich zu sein: Das war schon ein ziemliches Geschwurbel. Wir alle hier helfen mehr oder weniger gerne, aber ein bisschen Rücksicht in Form einer einigermassen aktuellen und korrekten Rechtschreibung wird eigentlich vorausgesetzt - nicht, weil wir die Fragenden quälen wollen, sondern weil wir uns nicht quälen wollen, wenn wir schon *gratis* Hilfe leisten.

Wenn noch Fragen offen sind, immer her damit, aber vielleicht nimmst du dir ein nächstes Mal ein bisschen Zeit zum Formulieren und Aufschreiben deiner Sätze, und wenn du fertig bist, solltest du deinen Beitrag vielleicht nochmals korrekturlesen - braucht ein bisschen Zeit, lohnt sich aber.

Gruss
cwriter
 
Und falls es noch nicht klar ist:
Dein Programm prüft nicht fehlerfrei, ob es eine Primzahl ist oder nicht
(nicht nur wegen der Programmierung, rein vom Prinzip her schon)
Die Faktoren 2, 3, 5 und 7 filtern ein paar Nicht-Primzahlen heraus, aber längst nicht alle.
 
Hi,

wenn ich mich als Mathe-Amateur mal zu Wort melden darf: Ich habe irgendwann irgendwo mal gelesen, dass man Nicht-Primzahlen (NP) daran erkennt, dass sie ohne Rest durch eine (oder mehrere) der Primzahlen < NP teilen kann.

Bspw. 15 ist keine Primzahl, weil sie sich ohne Rest durch 3 oder 5 teilen lässt. 17 ist eine Primzahl, weil sie sich nicht ohne Rest durch 1..16 teilen lässt.

Wenn also weder Speicher noch Rechengeschwindigkeit ein Aspekt ist, den das Programm zum Prüfen erfüllen soll, würde ich doch folgenden Ansatz vorschlagen:

0. Lege die höchste zu prüfende natürliche Zahl maxN fest
1. Alloziere ein dynamisches Feld "aP" mit sizeof(int) * maxN
2. Iteriere über alle natürlichen Zahlen n bis maxN.
3. In jedem Durchlauf prüfst du, ob die aktuelle n entweder 2, 3, 5 oder 7 ist und fügst sie dem dynamischen Feld hinzu, gibst aus, das aktuelle n eine Primzahl ist und machst continue.

4.a. Setze eine int Variable "kp" auf 0
4.b. Jetzt iterierst du über die gemerkten n in "ap" und prüfst ob die aktuelle Zahl n sich durch die aktuelle gemerkte NP ohne Rest teilen lässt. Wenn das der Fall ist, setze "kp" auf 1 und breche Iteration 2 ab.

5. Prüfe "kp" auf 0 und füge aktuelle n dem dynamischen Feld hinzu. Gebe aus, dass aktuelle n eine Primzahl ist.

Prüfen ob eine Zahl ohne Rest durch eine andere teilbar ist, kann man mittels dem Modulo-Operator auf 0. Bspw: 5 % 2 == 0 => falsch; 10 % 4 == 0 => falsch; 15 % 3 == 0 => richtig.
 
Zuletzt bearbeitet:
Hmm, das versteh ich jetzt grad nicht. Machen wir ein Beispiel:

Gegeben sei maxN = 100, x = 13, sqrt(x) = ~ 3,6

Gut, maxN ist hier natürlich mindestens ~3,6, aber wieso diese Einschränkung? Gibt es einen Fall, bei dem die Einschränkung nicht greift, bzw. wie kann nach dem Algo diese Einschränkung jemals false liefern?
 
Bzw. ich glaub grad, im hab den Sinn des Algos falsch verstanden :D

Was ich nur meinte, dass wenn man für eine einzelne Zahl X alle kleineren Zahlen k durchprobiert
(ob irgendwo X%k==0 ist), braucht man nur die k zwischen 1 (bzw. 2) und sqrt(X) aufgerundet.

Wenn es ein kgross größer als sqrt(X) und mit X%k==0 gibt,
dann erfüllt k = X/kgross auch die Bedingung X%k==0,
und dieses k ist kleiner als die Wurzel, also findet man es zuerst
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück