Primzahlen, mal wieder...
-
Guten Morgen allerseits.
Ich weiß, dass das in sämtlichen Foren schon sooo oft durchgekaut wurde, doch ich komme damit nicht auf meine Lösung und verzweifel langsam, wobei ich jetzt den Ergeiz habe, das Programm noch fertig zu stellen (evtl. noch zu erweitern
)Hier mein Quellcode...Was mache ich falsch? Er sagt mir, dass jede die ich eingebe, KEINE Primzahl ist?! Ich glaube mein Brett vorm Kopf wird immer dicker...
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> /*Eingabe der Primzahl, prüfen ob Primzahl ist, wenn JA, dann Ausgabe der Primzahl, wenn NEIN--Textausgabe*/ int main() { int zahl; int i,j; bool isprim; printf ("Primzahlberechnung \n\n\a"); scanf ("%d",&zahl); for (i=2;i<zahl;i++) { isprim == true; if (zahl % i ==0 ) { isprim == false; } if (zahl % i != 0 ) { isprim == true; } } if (isprim == true) { printf ("EINE Primzahl"); } if (isprim == false) { printf ("KEINE Primzahl"); } return 0; }
-
Hi,
die Zuweisungen sind falsch und es fehlt eine Abbruchbedingung in der for Schleife.#include <math.h> int main() { unsigned zahl, i, isprim = 1; printf ("Primzahlberechnung \n\n\a"); if ( 0 == scanf ("%d",&zahl)) return 0; for (i=2;i<=sqrt(zahl);i++) { if (zahl%i==0) { isprim = 0; break; } } if (isprim == 1) printf ("EINE Primzahl"); else printf ("KEINE Primzahl"); return 0; }
-
Hier mal ein einfaches Beispiel:
#include <stdio.h> #include <limits.h> int main( void ) { int zahl = 0; int multi = 0; int anz = 0; // Eingabe: fprintf( stderr, "Primzahl: " ); scanf ("%d",&zahl); for( multi = zahl; multi > 0; multi-- ) { if( ((zahl / multi)*multi) == zahl ) anz++; if( anz > 2 ) multi = 0; }; if( anz <= 2 ) fprintf( stderr, "Die Zahl %d ist eine Primzahl\n", zahl ); else fprintf( stderr, "Die Zahl %d ist keine Primzahl\n", zahl ); return 0; };Wobei ich mir nicht sicher bin, ob der Datentyp 'int' evtl. fehl am Platz ist.
mFg
-
Nabend und erstmal Danke für die hilfreichen Antworten. Habe mein Programm jetzt soweit fertig, doch würde ich gerne Anregungen haben um die Laufzeit zu verbessern?! Ich stehe irgendwie auf dem Schlauch.
Habe jetzt z.B. für die Zahl: 8734567890987654437 eine Laufzeit
von 4,557000 Sekunden. Frage: Geht das schneller?Gruß
Hier mein aktueller Quellcode:
#include <stdio.h> #include <stdlib.h> #include <time.h> int main() { // Variablendeklaration int Anzahl = 1, Durchlauf = 0; // Anzahl der zu berechnenden Zahlen und Durchlaufzähler unsigned long long Zahl = 1,Ursprungszahl = 1; // Vorzeichenlose Eingabe unsigned long long Teiler = 2; // Teilerzähler (wird in jedem Durchlauf Inkrementiert) time_t startzeit,endzeit; float laufzeit; printf("Wie viele Zahlen sollen berechnet werden? "); scanf(" %i",&Anzahl); /* Schleife um die gewählte Anzahl der zu testenden Zahlen durchlaufen zu lassen */ while (Durchlauf<Anzahl) { Durchlauf++; // Erhöhung des Durchlaufzählers printf("\n\nBitte geben sie nun ihre zu zerlegende Zahl ein! "); scanf("\n%I64u", &Zahl); Ursprungszahl = Zahl; // Vorbereitungstext und Eingabe der zubearbeitenden Zahl printf("\nWir testen %I64u auf Teiler!\n\n %I64u = ",Zahl,Zahl); /* Schleife, die so oft durchläuft, bis die eingegebenen Zahl 1 ist. Die Zahl wird durch einen ermittelten Teiler geteilt und wird dadurch kleiner. Wenn der Teiler die Zahl nicht teilt wird er erhöht und erneut getestet. */ startzeit = clock(); // Zeitabfrage vor der Berechnung while (Zahl>1) // Schleife zur Berechnung - Läuft so lange bis die Zahl = 1 ist, { // da 1 nicht mehr teilbar ist if (Zahl%Teiler==0) { Zahl=Zahl/Teiler; // Verminderung der Zahl, um Teiler des restes zu ermitteln if (Ursprungszahl==Teiler) // Primzahlentest (Ist der Teiler gleich der Ursprungszahl ist sie eine Primzahl) { printf("Primzahl!"); } else { printf ("%I64u", Teiler); // Teilerausgabe wenn sie keine Primzahl ist if (Zahl>1) { printf(" * "); } else { printf("\n"); } Teiler=2; // Teilerzurückstellung } } else { Teiler++; // Teilererhöhung wenn in "Zeile 49" keine Teilbarkeit ermittelt wurde } } endzeit = clock(); // Zeitabrage nach der Berechnung laufzeit = (endzeit - startzeit)/1000.0; // Laufzeit der Rechnung in ms, deshalb "x/1000" printf("\n Laufzeit: %f Sekunden\n", laufzeit); // Ausgabe der Laufzeit } return 0; }
-
Trenne mal die Rechnung von der Ausgabe. Ausgaben sind ungeheuer langsam und ziehen daher alles runter.
-
holtideluxe schrieb:
Habe jetzt z.B. für die Zahl: 8734567890987654437 eine Laufzeit
von 4,557000 Sekunden. Frage: Geht das schneller?Klar, mit asm, aber zuerst der Algorithmus. Ganz gut beschrieben hier:
http://de.wikipedia.org/wiki/Sieb_des_Eratosthenesbesser noch beschrieben in dem Buch "Der Zahlenteufel" von Enzensberger.
Du kannst es auch selbst versuchen, mit Papier und Bleistift. Dazu musst du eine Tabelle erstellen, wie auf der Wiki-Seite und dann alle Nichtprimzahlen streichen.
Die Visualisierung dieses Prinzip hilft verstehen und optimieren.
-
sieb hin oder her schau lies dir doch mal den wiki artikel durch da steht z.b. sowas
Jede Primzahl mit Ausnahme der 2 lässt sich einer der beiden Klassen „Primzahl der Form 4k + 1“ oder „Primzahl der Form 4k + 3“ zuordnen, wobei k eine natürliche Zahl ist. Darüber hinaus hat jede Primzahl p > 3 die Form p = 6k + 1 oder p = 6k − 1, wobei k eine natürliche Zahl ist. Nach dem dirichletschen Primzahlsatz gibt es in jeder dieser vier Klassen unendlich viele Primzahlen.
damit sollte eigentlich klar werden wo du nach den dingern suchen mußt...
lg lolo
-
SeppJ schrieb:
Trenne mal die Rechnung von der Ausgabe. Ausgaben sind ungeheuer langsam und ziehen daher alles runter.
oder einfach mal versuchen die ausgabe in eine datei umleiten
lg lolo
