Wie programmiere ich einen Primzahlenrechner?
Moin, ich habe im Wintersemester mit einem Maschinenbaustudium angefangen. Im Informatikunterricht sollten wir mit dem Programm stucturizer einen Primzahlrechner programmieren. Die ersten Anfänge habe ich auch hinbekommen kam ich nicht weiter als 3 und 2 schonmal als Primzahl auszuschließen. Ich hoffe ihr könnt mir vielleicht helfen?
Außerdem habe ich noch die Frage ob ihr vielleicht Möglichkeiten (Bücher, Videos, Lernplattformen) kennt sich dieses algorithmische Denken anzueignen.
LG
Felix
4 Antworten
int main(void)
{
int primzahl=1;
int dividable;
int skip=0;
while ( primzahl<1000000)
{
skip=1;
dividable=(primzahl-1);
while ( dividable>1){
if ( primzahl%dividable==0 ) skip=0; dividable-=1;}
if ( skip==1) printf("%d\n",primzahl);
primzahl+=1;
}
/* doublet type cast geht?!?!?! (wollte es erst noch mit Festkomma-Multiplikation zuvor versuchen, ergab aber irgendwie nur 1 statt 0 nach Division?!)*/
}
scheint zu gehen? es gibt und nicht nur gäbe noch schnellere Algorithmen, vielleicht, indem man rekursiv (verworfene?) Ergebnisse miteinander durchmultiplizierte?! weiß auch nicht, warum der Compiler bei der Festkommaarithmetik scheinbar float mit streikte?! eine Division gibt da stets ein float zurück oder nicht?!
Festkommaarithmetik wäre Integer-Werte vor Division hochmultiplizieren und danach entsprechend runtermultiplizieren, aber mit einer automatischen float-Konvertierung kann man mit einem Ergebnis von 0 auch kaum noch mit fabs()-Betrag prüfen, und das mit floats ist und wäre eh Verschwendung von Rechenleistung, ob es direkt ganzzahlig aufginge?!
Das ist ja wohl mal innerhalb von 5 Minuten programmiert. Modulo operator in einer schleife hilft hier. if(eingabe % testzahl == 0 ){...} // ist keine primzahl
eingabe = 41
for (testzahl = 2; testzahl < eingabe; testzahl++) {
if (eingabe % testzahl == 0) {
//ich bin KEINE primzahl weil ich durch testzahl teilbar bin
break;
}
}
Ich verstehe diese Schritte nicht. Wenn 5%5 = 0 dann keine Primzahl. Aber 5 ist eine Primzahl.
Okay nun ist aber nicht jede Zahl die nicht durch zwei teilbar ist eine Primzahl
Wird im Skript geprüft ob die eingabe durch eine testzahl teilbar ist mit restwert 0
Was ich meine ist: Wenn der Rest nicht Null ist dann ist es ja laut dem Programm eine Primzahl. Der Rest von 133/2 ist nicht gleich Null. 133 ist aber trotzdem keine Primzahl.
133 ist durch 7 teilbar, also kommt rest 0 raus (133 % 7) ! Somit keine Primzahl wie es oben im Skript steht!!!!
Willst du schnell große Anzahlen an Primzahlen ermitteln, ist dies recht aufwändig. Aber einfache Algorithmen gibt es ebenfalls. Hervorzuheben wäre da das Primzahlensieb, zu googlen under "Sieb des Eratosthenes". Im Prinzip ein bit-array, in dem du ganzzahlige Vielfache jeder nächsten ermittelten Primzahl bis zum Arrayende als nicht-prim markierst.
was ist in diesem fall die eingabe und was ist die Testzahl?