primzahlen
-
wenn du weisst, was eine primzahl ist, solltest du in der lage sein, selbst auf einen simplen algorithmus zu entwerfen.
-
bitte !
ich weiss auch was eine primzahl ist, eine zahl die durch eins und durch sich selbst teilbar ist ! ich jhabe auch von einem fermat algorithmus gelesen, weiss aber leider nicht, deen umzusetzen !!
bitte helft mir !!
danke !
-
ich geb mal einen tipp:
gib die zahl ein die du testen willst...und lass sie durch alles bis zahl-1 auf rest prüfen! (natürlich erst bei 2 anfangen)
sollte nirgends ein rest 0 auftauchen, ist es eine primzahl!
-
danke, hat sich erledigt ...
-
5er1al schrieb:
gib die zahl ein die du testen willst...und lass sie durch alles bis zahl-1 auf rest prüfen! (natürlich erst bei 2 anfangen)
(zahl/2)-1 meinst du wohl?
@threadstarter hab ich in irgendeinem wort programmiersprache erwähnt?
-
otze schrieb:
(zahl/2)-1 meinst du wohl?
dann gleich sqrt(zahl).
-
wieso wurzel?
-
(zahl/2)-1 ist ganz sicher nicht die Wurzel.
Nur ein Bsp.:
sqrt(16) = 4
(16/2)-1 = 7Noch ein Hinweis zu den Primzahlen: Daran denken, dass die 1 keine Primzahl ist, auch wenn sie durch sich selbst und durch 1 teilbar ist.
-
Evolver schrieb:
(zahl/2)-1 ist ganz sicher nicht die Wurzel.
Nur ein Bsp.:
sqrt(16) = 4
(16/2)-1 = 7das hat er nicht gemeint.
er meinte: wenn man schon die möglichkeiten soweit einschränkt, kann man noch einen schritt weitergehen.
-
was versteht ihr nich?
Ich meine, das die Zahl die man überprüfen will, einfach durch alles geteilt wird, bis zahl-1 (also wenn man 17 testen will, dann 17 durch alles teilen bis 16)!
Bei 2 erst anfangen, weil JEde Zahl durch 1 teilbar ist, egal ob prim oder nciht!
Müsste eigentlich stimmen...
-
5er1al schrieb:
was versteht ihr nich?
Ich meine, das die Zahl die man überprüfen will, einfach durch alles geteilt wird, bis zahl-1 (also wenn man 17 testen will, dann 17 durch alles teilen bis 16)!
Bei 2 erst anfangen, weil JEde Zahl durch 1 teilbar ist, egal ob prim oder nciht!
Müsste eigentlich stimmen...
Es geht nur darum die Möglichkeiten weiter einzuschränken, den in der Form ist der Algorithmus nicht besonders effizient.
-
naja, und wie willst möglichkeiten weiter einschränken?
-
Dieser Thread wurde von Moderator/in HumeSikkins aus dem Forum C++ in das Forum Mathematik verschoben.
Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?Dieses Posting wurde automatisch erzeugt.
-
naja, eben dass man die anzahl der zu überprüfenden zahlen minimiert. also nicht bis zahl-1 überprüfen, das ist quark.
denn wenn man zahl durch irgendetwas zwischen zahl/2+1 und zahl teilt, so bekommt man als ergebnis nie etwas ganzzahliges. das ergebnis kann nur noch zwischen 1 und 2 liegen.
weiter kann man das dann eben noch einschränken, wie schon von volkard geschrieben, indem man nichtmal bis zahl/2 überprüft, sondern nur bis zur wurzel von zahl.
beispiel:zahl = 37
sqrt(zahl) ~ 6,1 also etwa 6
zahl/2 -> nicht ganzzahlig
zahl/3 -> auch
zahl/5 -> auch
-> 37 = primzahl
weiter muss ich nich überprüfen, denn wenn ich noch zahlen > 6.1 überprüfe, also z.b. 7, dann kann als ergebnis der division nur noch etwas kleiner als 6.1 herauskommen. und die zahlen haben wir schon überprüft.ich hoffe mal dass ich jetzt keinen quatsch geschieben hab!
-
naja, so ein matheass bin ich dann auch nicht
-
ja da hat nubian recht das sollte reichen !
also wenn da mehrere zahlen überprüft werden sollen, würde ich vorschlagen das "Sieb des Erathosthenes" empfehlen (ich weiss nicht ob das hier jemand kennt) also das is wenn man ne primzahl kennt, dann kann man alle vielfachen davon als primzahlen ausschliesen, also kann man einen boolvektor anlegen, der alle zahlen die primzahlen sind auf true hat.
dann beginnt man zb. in dem man einen vektor mit 100 boolelementen anlegt und dann beginnt man mit 2 denn 2 is ja eine primzahl, also schaltet man 4,6,8 und so weiter auf false....
dann macht man bei der nächsten zahl, die noch true(also eine primzahl ist) weiter, das wäre dann 3 und schaltet alle vielfachen von 3 auf false, also 6,9 und so weiter.
dann geht man zur nächsten zahl die true hat (also 5) und macht dort das selbe.
am ende hat man dann einen vektor bei dem alle primzahlen auf true sind und alle nicht-primzahlen auf false.
dann braucht man nur noch nach jeder eingabe prüfen ob der schalter mit dem index true oder false ist und dann hat man das ergebnis. also ich weiss wirklich nicht wie die laufzeit dabei is, aber ich denke wenn man jetzt 20 zahlen eingeben will und jedesmal durch alles teilen muss geht es mit dem vektor schneller, aber das is sicher ansichtssache.
naja ich hoffe es hat überhaupt jemand geblickt .....
vielleicht kanns ja jemand brauchen ....
mfg _Ocin_
-
das problem ist die größe des feldes un der speicherverbrauch.
dazu kommt noch, dass das anlegen des vectors(falls man die werte nicht selber eingibt) unter umständen recht lange dauern kann.
-
vector<bool> ist ganz sicher eine schlechte idee. die grösse des siebs ist eigentlich nicht das problem, man kann ja scheibchenweise sieben.
-
ja ich hab ja gesagt das das mit der laufzeit und dem speicherplatz ne andere frage is aber ich wollt einfach nur mal posten, wie es gemacht werden kann, denn ich denke wenn ich dann unmengen an zahlen prüfen will, dauert das mit dem teilen jedesmal bestimmt noch länger.
auserdem bin ich selber noch nicht so lange im geschäft
und deshalb lass ich mich da auch gerne korrigieren ....
-
Nach dem kleinen Fermatschen Satz ist (2^b-2)mod b=0, wenn n eine Primzahl ist. Und das Tolle: In fastz allen anderen Fällen erhältst du eine Zahl ungleich Null. Wenn du nun b=2 setzt, hast du einen schnellen Test, um die meisten Zahlen als nicht-prim zu entlarven. Dummerweise kann das Verfahren aber bei sogenannten Pseudoprimzahlen versagen. Musst dann also immernoch testen, sollte der Wert doch Null sein.