Primzahlen
-
Waldschatten schrieb:
Ja, da gibt es eine mit zwei Schleifen, die eigentlich sehr verständlich ist.
Verständlich, aber leider falsch. 2 ist eine Primzahl.
-
Ist dir das Sieb des Eratosthenes schon zu mathematisch? Das ist eine recht einfach zu verstehende Methode. Mit ihr kann man alle Primzahlen bis hin zu einem bestimmten Wert bestimmen. Und auch recht effizient für diese Aufgabe.
Ansonsten gibt es noch jede Menge Algorithmen um festzustellen ob eine Zahl eine Primzahl ist (von einfach zu verstehen bis hin zu hochmathematisch). Wäre das auch was für dich?
Und es gibt noch eine Reihe Formeln um einem gute Kandidaten für Primzahlen zu liefern, die man dann mit genannten Algorithmen überprüfen kann. Diese reichen von simpel, über empirisch(d.h. leicht umzusetzen, aber unverstanden) bis hin zu hochkomplex.
Eine extrem effiziente, aber häufig verpönte, Methode zur Generierung kleiner Primzahlen (d.h. mit weniger als ein paar zig Stellen) ist übrigens die Tabellierung.
-
Man bezeichnet eine Zahl dann als Primzahl, wenn sie nur durch 1 und sich selber teilbar ist. Die Zahl 0 und 1 sind jedoch per Definition keine Primzahlen.
Es gilt also einen Algorithmus zu schreiben, der für eine gegebene Zahl überprüft, ob es außer der 1 und der Zahl selber noch weitere Teiler gibt.
Überprüfen lässt sich das indem man testet, ob bei der Division ein Rest bleibt. Das geht mit dem Modulo-Operator %.
Nehmen wir nun als Beispiel die Zahl 7.
7 durch 1 = geht (erster Teiler)
7 durch 2 = geht nicht
7 durch 3 = geht nicht
7 durch 4 = geht nicht
7 durch 5 = geht nicht
7 durch 6 = geht nicht
7 durch 7 = geht (zweiter Teiler)Es gibt nur zwei Teiler: 1 und 7, also ist 7 eine Primzahl.
Nehmen wir als weiteres Beispiel die Zahl 9.
9 durch 1 = geht (erster Teiler)
9 durch 2 = geht nicht
9 durch 3 = geht (zweiter Teiler)
...
9 durch 9 = geht (dritter Teiler)An dieser Stelle kann man aufhören, da es mehr als zwei Teiler gibt. Nämlich die 1, 3 und 9. Es handelt sich also um keine Primzahl.
Man kann das sehr einfach programmieren. Der Algorithmus ist dann zwar langsam, aber er ist klar verständlich. Dann kann man ran gehen und das immer weiter optimieren.
Sollte nicht allzu schwer sein.
-
-
SeppJ schrieb:
Eine extrem effiziente, aber häufig verpönte, Methode zur Generierung kleiner Primzahlen (d.h. mit weniger als ein paar zig Stellen) ist übrigens die Tabellierung.
Was meinst Du mit Tabellierung?
-
...... schrieb:
Man bezeichnet eine Zahl dann als Primzahl, wenn sie nur durch 1 und sich selber teilbar ist. Die Zahl 0 und 1 sind jedoch per Definition keine Primzahlen.
Es gilt also einen Algorithmus zu schreiben, der für eine gegebene Zahl überprüft, ob es außer der 1 und der Zahl selber noch weitere Teiler gibt.
Überprüfen lässt sich das indem man testet, ob bei der Division ein Rest bleibt. Das geht mit dem Modulo-Operator %.
Nehmen wir nun als Beispiel die Zahl 7.
7 durch 1 = geht (erster Teiler)
7 durch 2 = geht nicht
7 durch 3 = geht nicht
7 durch 4 = geht nicht
7 durch 5 = geht nicht
7 durch 6 = geht nicht
7 durch 7 = geht (zweiter Teiler)Es gibt nur zwei Teiler: 1 und 7, also ist 7 eine Primzahl.
Nehmen wir als weiteres Beispiel die Zahl 9.
9 durch 1 = geht (erster Teiler)
9 durch 2 = geht nicht
9 durch 3 = geht (zweiter Teiler)
...
9 durch 9 = geht (dritter Teiler)An dieser Stelle kann man aufhören, da es mehr als zwei Teiler gibt. Nämlich die 1, 3 und 9. Es handelt sich also um keine Primzahl.
Man kann das sehr einfach programmieren. Der Algorithmus ist dann zwar langsam, aber er ist klar verständlich. Dann kann man ran gehen und das immer weiter optimieren.
Sollte nicht allzu schwer sein.
-----------------------
Danke, wußte doch mit 2 Schleifen und MODULO muß es ja gehen.
Grazie, noch mal.
Werner23
P.S.: Unter welcher Adresse kann ich ein C-Forum finden ?
Hab jetzt noch bis Freitag (Prüfung) C... und dann beginnen wir mit C++.
-
Schau mal hier in diesem Forum unter "ANSI C" (ein Subforum höher)...
-
Wenn Du genau eine Zahl auf Primzahl prüfen möchtest, dann brauchst Du sogar nur eine Schleife!
lg, freakC++
-
-
volkard schrieb:
SeppJ schrieb:
Eine extrem effiziente, aber häufig verpönte, Methode zur Generierung kleiner Primzahlen (d.h. mit weniger als ein paar zig Stellen) ist übrigens die Tabellierung.
Was meinst Du mit Tabellierung?
Ich nehme an, er meint, sich eine gewisse Anzahl von Primzahlen vorzuhalten. Das "primes"-Programm aus bsdgames macht das so; es hält eine große Tabelle aller Primzahlen < 2^16 vor und kann so sehr schnell Primzahlen < 2^32 generieren.
-
volkard schrieb:
SeppJ schrieb:
Eine extrem effiziente, aber häufig verpönte, Methode zur Generierung kleiner Primzahlen (d.h. mit weniger als ein paar zig Stellen) ist übrigens die Tabellierung.
Was meinst Du mit Tabellierung?
Eine Wertetabelle der ersten X Primzahlen. Ist gut geeignet für einen Jumpstart der Siebmethode. Außerdem hängt man damit auf naiven Programmierwettbewerben (wo die Leute dann "schöne" Algorithmen bauen die selbst die 2 als Primzahl erstmal berechnen müssen) alles ab
.
