Primzahl Test
-
hallo,
habe ein kleines Problem. Ich soll ein kleines Programm erstellen, was diverse Berechnungen durchführen soll. Es klappt ja auch alles außer, dass das bei der Primzahlüberprüfung das Programm absürzt! Ich bitte um eure Hilfe
#include <stdio.h> #include <stdlib.h> #include <math.h> int main() { int Eingabe, Zahl, ersteZahl, zweiteZahl; int Potenz, Exponent, Ergebnis, Prim, i; float Wurzel; char Antwort; printf("\nDas Programm fuehrt verschiedene Berechnungen durch!\n"); printf("Eingabe-> 1: Wurzel aus einer positiven ganzen Zahl berechnen.\n"); printf(" 2: N hoch m fuer n, m natuerliche Zahl inkl. 0 berechnen.\n"); printf(" 3: N hoch m fuer n, m ganze Zahl inkl. 0 berechnen.\n"); printf(" 4: Die ersten n Fibonaccizahlen fuer die Eingabe von n ausgeben.\n"); printf(" 5: Ob die Eingabe von n eine Primzahl ist.\n\n"); do { printf("Bitte geben Sie Ihre Eingabe (1-5) ein: "); scanf("%d", &Eingabe); if(Eingabe==1) { printf("Bitte geben Sie jetzt eine positive ganze Zahl ein: "); scanf("%d", &Zahl); if(Zahl >= 0) { Wurzel = sqrt(Zahl); printf("Die Wurzel aus %d betraegt = %.3lf.\n", Zahl, Wurzel); } else { printf("Die eingegebene Zahl ist negativ und kann daher nicht berechnet werden!\n"); } } if(Eingabe==2) { printf("Bitte geben Sie eine natuerliche Zahl fuer n als Potenz und m als Exponent!\n"); printf("Bitte geben Sie die Potenz ein: "); scanf("%d", &Potenz); printf("Bitte geben Sie den Exponent ein: "); scanf("%d", &Exponent); if(Potenz>=0 && Exponent>=0) { Ergebnis = pow(Potenz,Exponent); printf("Das Ergebnis fuer n=%d und m=%d betreagt = %d.\n", Potenz, Exponent, Ergebnis); } else { printf("Die Eingabe ist fehlerhaft und kann daher nicht berechnet werden!\n"); } } if(Eingabe==3) { printf("Bitte geben Sie eine ganze Zahl fuer n als Potenz und m als Exponent!\n"); printf("Bitte geben Sie die Potenz ein: "); scanf("%d", &Potenz); printf("Bitte geben Sie den Exponent ein: "); scanf("%d", &Exponent); Ergebnis = pow(Potenz,Exponent); printf("Das Ergebnis fuer n=%d und m=%d betreagt = %d.\n", Potenz, Exponent, Ergebnis); } if(Eingabe==4) { ersteZahl = 0; zweiteZahl = 1; printf("Geben Sie eine Zahl ein, die die Fibonacci-Folge ausgibt: "); scanf("%d", &Eingabe); if(Eingabe>=0) { printf("1\t%.0f\n2\t%.0lf\n", ersteZahl, zweiteZahl); for(i = 0; i < (Eingabe - 2); ++i) { Ergebnis = (ersteZahl + zweiteZahl); printf("%d\t%.0lf\n", i+3, Ergebnis); ersteZahl = zweiteZahl; zweiteZahl = Ergebnis; } } else { printf("Die eingegebene Zahl ist kleiner 0 und kann daher nicht ausgegeben werden!\n"); } } if(Eingabe==5) { printf("Bitte geben Sie eine Zahl zum Ueberpruefen ein: "); scanf("%d", &Eingabe); for(i=2; i<Prim; i++) { if ( Prim % i == 0 ) { printf("%d ist keine Primzahl\n", Prim); break; } else { printf("%d ist eine Primzahl\n", Prim); } } } printf("Moechten Sie noch eine Berechnung durchfuehren? j/n: "); scanf("%s", &Antwort); } while(Antwort=='j'); printf("Das Rechenprogramm wurde beendet! Aufwiedersehen.\n"); return EXIT_SUCCESS; }
-
Was genau meinst du mit "abstürzen"?
Schau dir mal diese beiden Zeilen noch mal an (bzgl. der Variablen):
scanf("%d", &Eingabe); for(i=2; i<Prim; i++)Desweiteren ist deine Primzahlerkennung falsch, aber das wirst du dann sehen, sobald dein Programm korrigiert ist und läuft...
-
du hast recht. die Variable ist jetzt richtig, die primzahlerkennung läuft wirklich nicht wie sie laufen soll. wenn ich eine höhere Zahl eingebe, wie z.B. 77 kommt dann diese Ausgabe raus:
77 ist eine Primzahl 77 ist eine Primzahl 77 ist eine Primzahl 77 ist eine Primzahl 77 ist eine Primzahl 77 ist keine Primzahl
-
Die Schleife sieht bei dir so aus:
for(i=2; i<Prim; i++) { //... }Hier würde es reichen, wenn man die bis Prim/2 laufen lässt.
Außerdem ist 77 keine Primzahl...Edit: Wenn du nicht willst, dass so viele Ausgaben gemacht werden, könntest du ja in einer Variablen sie Anzahl der gefundenen Teiler speichern. Wenn 0 herauskommen sollte, ist die Zahl eine Primzahl.
-
Haki schrieb:
du hast recht. die Variable ist jetzt richtig, die primzahlerkennung läuft wirklich nicht wie sie laufen soll. wenn ich eine höhere Zahl eingebe, wie z.B. 77 kommt dann diese Ausgabe raus:
Und da heisst es immer, dass imperatives Programmieren einsteigerfreundlich ist... ich glaub nicht so recht dran.
Bei jedem Schleifendurchlauf trifft entweder der then-Teil oder der else-Teil zu (klar, oder?). Wenn kein Rest bleibt, kann's keine Primzahl sein, dass stimmt. Aber wenn beim n-ten i ein Rest bleibt, heisst das noch nicht, dass es eine Primzahl ist. Es ist erst dann sicher eine Primzahl, wenn für alle i ein Rest bleibt.
-
Jochen S. schrieb:
Hier würde es reichen, wenn man die bis Prim/2 laufen lässt.
Oder gleich nur bis sqrt(Prim).
Jochen S. schrieb:
Wenn du nicht willst, dass so viele Ausgaben gemacht werden, könntest du ja in einer Variablen sie Anzahl der gefundenen Teiler speichern.
Das wäre nicht nur Primzahltesten sondern Teilerzählen. Wenn man nur testen will, muss man nur im richtigen Moment rausspringen.
-
ok hab das gemacht mit dem sqrt. Habe jetzt immernoch zwei Probleme und zwar....
wenn 1,2 oder 3 eingebe wird nichts ausgegeben.habe versucht i kleiner zu machen aber es ging trotzdem nicht. das zweite Problem ist das jede zahl, die mit 7 endet, wie z.B. 77, 187 oder 987, ist immer eine Primzahl. ansonsten funktionert dir funktion einwandfreifor(i=2; i<=sqrt(Prim); i++) { if ( Prim % i == 0 ) { printf("%d ist keine Primzahl!\n", Prim); break; } else { printf("%d ist eine Primzahl!\n", Prim); break; } }
-
schau dir mal an, was sqrt zurueckliefert.
fuer den Fall von 77 kommt bei sqrt(77) der wert 8.xxx heraus. Deine Schleife
geht also nur bis zur 8. 77 ist aber auch durch 11 teilbar. sqrt ist also nicht der richtige Weg. X/2 wie von Jochen erwaehnt ist da etwas besser.die Werte fuer 1,2 und 3 kannst gleich abfangen. (Prim <= 3)
-
Aaaaaber 77 ist durch 7 teilbar. und 7 is kleiner als 8.xx.
Bis zur Wurzel reicht vollkommen.
-
stimmt *LOL* ... hab heut nen schlechten Tag.Allerdings wuerde ich dann mit einer Status-Variablen (bool) arbeiten, die auf false gesetz wird, wenn eine Bedingung x%x == 0 liefert.
Das Break fuehrt dazu, dass 77%2 > 0 liefert und dann die Schleife schon abbricht
-
So könnte man es machen:
int IsPrim(int Prim) { int iPrim = 1; int i; for(i=2; i<=sqrt(Prim); i++) { if ( Prim % i == 0 ) { iPrim = 0; break; } } return iPrim; }Finde das mit der Funktion irgendwie schöner...
MfG, Jochen
-
BasicMan01 schrieb:
Allerdings wuerde ich dann mit einer Status-Variablen (bool) arbeiten, die auf false gesetz wird, wenn eine Bedingung x%x == 0 liefert.
Jochen S. schrieb:
So könnte man es machen:
...Nicht vergessen: C ist C, da darf man sich's einfach machen:
#include <stdbool.h> bool isprime(int number) { int limit = sqrt(number); for (int i = 2; i <= limit; i++) if (number % i == 0) return false; return true; }Sicherheitshalber das sqrt(number) aus der for-Bedingung rausnehmen, es muss schon ein ausgefeilter Compiler sein, damit er sowas optimiert.
Jochen S. schrieb:
Finde das mit der Funktion irgendwie schöner...
Das war noch mal...?
Edit: Schon klar...
-
Gut, das würde auch in C++ funktionieren. (Auch ohne das Einbinden von stdbool.h)
Finde meine Funktion aber schöner.
-
Jochen S. schrieb:
Gut, das würde auch in C++ funktionieren. (Auch ohne das Einbinden von stdbool.h)
Finde meine Funktion aber schöner.F1) Sind negative Zahlen und die Zahlen 0,1 Primzahlen?
F2) Muss man gerade Zahlen > 2 nach dem ersten Test auch weiterhin als Teiler berücksichtigen? :p
A1) Nöööööö!
A2) Siehe A1
-
Big Brother schrieb:
F1) Sind negative Zahlen...
7 /-7=-1 7 / 7= 1 -7/-7= 1
wenns mal wieder länger dauert
http://de.wikipedia.org/wiki/Miller-Rabin-Testlg lolo
-
noobLolo schrieb:
7 /-7=-1 7 / 7= 1 -7/-7= 1Äh ... na und?
Ich wollte auf den unpassend gewählten Datentypen int hinaus.
Das hätte ich wohl dazu schreiben sollen
-
Eigentlich reicht es zuerst auf %2 zu prüfen und dann die zählvariable um 2 zu erhöhen (da alle geraden zahlen eh durch 2 teilbar sind).
dadurch spart man sich unnötige schleifendurchläufe.bool isprime(int number) { int limit = sqrt(number); if ( number % 2 == 0) { return false; } for (int i = 3; i <= limit; i=i+2) { if (number % i == 0) { return false; } } return true; }
-
o_O schrieb:
Eigentlich reicht es zuerst auf %2 zu prüfen und dann die zählvariable um 2 zu erhöhen (da alle geraden zahlen eh durch 2 teilbar sind).
dadurch spart man sich unnötige schleifendurchläufe.Und was ist mit unnötigen Vielfachen von 3? Oder 5?
-
mngbd schrieb:
o_O schrieb:
Eigentlich reicht es zuerst auf %2 zu prüfen und dann die zählvariable um 2 zu erhöhen (da alle geraden zahlen eh durch 2 teilbar sind).
dadurch spart man sich unnötige schleifendurchläufe.Und was ist mit unnötigen Vielfachen von 3? Oder 5?
Die 3 geht noch relativ leicht, zum Beispiel for(s=2,i=5;...;i+=s,s=6-s)
Mit der 5 muß man wohl schon ein Array benutzen. Es ist schwierig, abzuschätzen, wie weit man es treiben kann, ohne durcvh die Komplexität wieder langsamer zu werden.
Ist eigentlich for (int i = 3; i <= limit; i=i+2) besser als for (int i = 3; i*i <= number; i=i+2)? Sind es ausreichend viele Ausstiege bei kleinen i, so daß die teure Wurzel oft genug gespart wird?
-
so hätt ichs mal versucht
int isPrime(int num){ if(num % 2 == 0 || num % 3 == 0 || num % 5 == 0) return 0; unsigned l = sqrt(num); l += 6 - l % 6; while(l-=6){ if(num % (l+1) == 0 || num % (l-1) == 0){ return 0; } } return 1; }lg lolo
