Wie berechnet man eigentlich eine Primzahl?
Hey,
muss für eine Programmieraufgabe in C ein Programm schreiben wo der Benutzer eine Primzahl eingibt und das Programm berechnen soll, ob es sich dabei um eine Primzahl handelt. Un da ich nicht wie ein kleiner Lümmel fragen möchte, ob ihr meine Programmier-Hausaufgabe machen könnt, bitte ich einfach nur darum, wie man eine Primzahl berechnet, ich komme einfach nicht dahinter.
Danke im Vorraus.
8 Antworten
zuerst prüfst du, ob die eingegebene Zahl mit Einerstelle = 0 2 4 6 oder 8 ist. Ist das der Fall hast du schonmal einen Faktor 2 und wenn die Zahl dann größer 2 war, ist sie keine Primzahl: fertig.
das selbe mit der Endziffer 5 und dem Faktor 5. Ist die Zahl dann größer 5, keine Primzahl: fertig.
dann die einzelnen Ziffern der Zahl addieren wenn diese größe 3 ist. Ist das Ergebnis ganzzahlig durch 3 teilbar, so war es keine Primzahl: MOD Funktion. fertig.
Ist der Algorithmus noch nicht fertig, dann folgendes:
starte mit Testfaktor 7
Wiederhole solange wie Testfaktor * Testfaktor <= Primzahl.
teste mit MOD Funktion ob ganzzahlig durch Testfaktor teilbar. wenn ja, dann fertig --- keine Primzahl.
Testfaktor um 2 erhöhen,
wenn wie oben durch 2, 3 oder 5 teilbar, dann erneut Testfaktor um 2 erhöhen, solange bis eben nicht durch 2,3 oder 5 teilbar.
End Wiederhole.
Zahl ist Primzahl, wenn in der Schleife kein Abbruch erfolgte.
Um das ganze zu beschleunigen kannst du noch die ersten 100 Primzahlen in ein Array speichern und dann erst das Array druchlaufen ob die Zahl drin ist. Ist sie nicht drin und kleiner der größten im Array, ist sie keine Primzahl. Ist sie drin dann ist sie Primzahl. Nur wenn die Zahl also größer der größten im Array befindlichen Zahl ist kommt dann der obige Algorithmus zum Laufen.
Problem ist jetzt nur noch der Datentyp. Für Primzahlberechnung darfst du nicht float nehmen sondern eine großen positiven int Typ. Aber selbst der größte int Typ ist evtl. zu klein. Aber ich schätze soweit will der Lehrer das nicht ausgearbeitet wissen.
Vielleicht solltest Du, bevor Du ein Programm zu Primzahlen schreibst, Dir wenigstens die Grundlagen zum Thema reinziehen?
wie oben beschrieben: ausnahme natürlich die 2 und die 5 selbst sind Primzahlen.
aber wie im endsatz beschrieben: das eigentliche problem wird der datentyp ... denn man will nicht etwa primzahlen bis 4 milliarden ... sondern primzahlen von 30-stelligen integern (dezimal gelesen) ... so und nun ? das wird jetzt kompliziert.
lehrer also fragen ob der maximal verfügbare int datentyp den die programmiersprache bietet genügt: long unsigned int zum beispiel. wenn nicht ... dann musst du noch überstunden machen ;-)
und verschwiegen soll auch nicht werden, dass es mathematishe verfahren gibt, die es noch schneller machen ... aber solange die sache mit dem datentyp bei unsigned long int bleibt spielt das dann keine rolle ,,, denn dann ists schnell genug, erst wenn du auf mind 30 stellen zahlen aufpustest solltest du dir diese mathematischen verfahren reinziehen.
Es geht doch um einen kleinen lustigen Algorithmus, und sicher nicht um eine mathematisch bestoptimierte Version für Riesenzahlen.
eine P kann man nicht berechnen mit einer formel.
f ( P ) = .....
eine Primzahl ist dann ermittelt, wenn man festgestellt hat , daß z.B 53 durch keine ganze Zahl außer 1 und 53 teilbar ist . Dabei reicht es , durch alle ganzen und ungeraden Zahlen zu teilen , die kleiner sind als Wurzel aus (53) , also .....<= 7.
Bei 100 000 sind es "nur" 316/2.
PS : Besser als Erastothenes ist dieses Sieb
- Falls die Testzahl eine gerade Zahl und nicht zwei ist: Keine Primzahl
- Dann nimmst du die Wurzel der Zahl
- Dann testest du mit allen ungeraden Zahlen von 3 bis zur Wurzel, ob Zahl MOD Testzahl verschieden 0 ist.
- Falls alles erfüllt -> Testzahl=Primzahl
Du probierst bis maximal zur Hälfte alle Primzahlen als Teiler durch, denn das sind die Zahlen, die kein Vielfaches eines vorigen Teilers sind. Wenn keinen findest, ist die Zahl eine Primzahl.
Beispiel:
101
Die Hälfte ist 50
Nicht teilbar durch 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, also Primzahl.
Hier, muss nur noch von C++ an C angepasst werden :
https://de.wikibooks.org/wiki/Algorithmensammlung:_Zahlentheorie:_Sieb_des_Eratosthenes#C++
Das Programm funktioniert, kannst du hiermit ausprobieren :
https://www.jdoodle.com/online-compiler-c++
Die Zahleneingabe muss in der Stdin Inputs... - Box erfolgen, und dann nochmal auf Execute geklickt werden.
das programm gibt eine liste von primzahlen aus und nicht ob die eingegebene eine primzahl ist. das gesuchte programm muss also nur eine antowrt "Primzahl", oder "keine Primzahl" geben.
Wenn die Zahl in der Liste nicht mit dabei ist, dann ist sie auch keine Primzahl ;-))
Ist sie aufgelistet, dann ist es eine Primzahl ;-))
ist aber blödsinn speicher zu reservieren. evtl. kackt der rechner mit out of memory ab, weil eben keine 100 billionen integer speichern kann in dem stroke.
ok 100 billionen war übertrieben. aber man sollte schon zumindest die zahl: 4 milliarden eingeben können was dann bestimmt mind. 5 millionen integer primzahlen (keine ahnung wieviel genau, aber sicher mehr als zig-tausend) erzeugt. und das wird dann der rechner schon verweigern.
aber für den ersten schritt meines algoritmus erstmal nicht schlecht ... dann aber nur bis maximal 1000 und nicht dauernd neu berechnen sondern einmal als seperates programm ausfühjren und die liste fest rein stellen als fix zahlen.
Wenn du es ohne Speicher haben willst, dann geht es auch Brute-Force, hier mal ein QBASIC - Programm :
DEFDBL A-Z
CLS
INPUT "Welche Zahl soll geprueft werden ( > 1) "; z
Merke = 0
FOR i = 2 TO (z - 1)
IF INT(z / i) = (z / i) THEN Merke = 1
NEXT i
IF Merke = 0 THEN PRINT "Die Zahl ist eine Primzahl."
IF Merke = 1 THEN PRINT "Die Zahl ist keine Primzahl."
END
Dieses Programm verbraucht praktisch keinen Speicherplatz, ist aber langsam.
Für Zahlen in der Nähe von 1000000000 werden bereits mehrere Sekunden Rechenzeit benötigt.
ist ja auch dumm programmiert ... denn du brauchst ja nicht bis zu z-1 laufen sondern nur bis i quadrat größer gleich z ist. und dann brauchst du nicht jede zahl prüfen sondern erstmal nur jede 2te und dann keine die mit 5 ended und dessen quesrumme bereits druch 3 teilbar ist. zumindest das step 2 ist leicht hinzufügbar und würde schon die zeit halbieren. dann mit dem i quadrat nochmal merklich.
achja .. und zu guter letzt: sobald Merke = 1 ist, kann von der Schleife rausgesprungen werden und muss nicht noch mehr geprüft werden. Der Datentyp ist auch bedenklich, evtl. nimmt Basic da dann float bei zwischenergebnis (z / i) und ist ungenau ... also der datentyp muss spezifiziert werden auf interger typen.
Ja. da hast du recht, bei Merke = 1 kann man die Schleife verlassen, habe ich auf die Schnelle übersehen.
Also :
DEFDBL A-Z
CLS
INPUT "Welche Zahl soll geprueft werden ( > 1) "; z
Merke = 0
FOR i = 2 TO (z - 1)
IF INT(z / i) = (z / i) THEN Merke = 1: EXIT FOR
NEXT i
IF Merke = 0 THEN PRINT "Die Zahl ist eine Primzahl."
IF Merke = 1 THEN PRINT "Die Zahl ist keine Primzahl."
END
Das mit den DEFDBL ist bei QBASIC so eine Besonderheit, das gibt es keine Probleme, DEFDBL sorgt sogar dafür dann man bis 999999999999998 gehen kann, ohne Probleme. Ist also besser als Integer.
Und hier mit der Änderung STEP 2 die du vorgeschlagen hast :
DEFDBL A-Z
CLS
INPUT "Welche Zahl soll geprueft werden ( > 1) "; z
Merke = 0
FOR i = 2 TO (z - 1) STEP 2
IF INT(z / i) = (z / i) THEN Merke = 1: EXIT FOR
NEXT i
IF Merke = 0 THEN PRINT "Die Zahl ist eine Primzahl."
IF Merke = 1 THEN PRINT "Die Zahl ist keine Primzahl."
END
Anmerkung :
Die Rechenzeit ist bis etwa 10000000019 erträglich, also im 10 Milliarden-Bereich.
Und das Programm liefert auch das korrekte Ergebnis, dass das eine Primzahl ist.
Heißt das, dass alle Zahlen mit 0,2,4,6,8,5 in der einerstelle keine Primzahlen sind?