Wie berechnet man eigentlich eine Primzahl?

9 Antworten

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.

Hälfte ist zuviel. Bis zur Wurzel genügt!

1

Stimmt, das macht Sinn.

0

Mach einen Aufruf von factor und teste return value.

Ansonsten: Testdivisionen durch die ersten Primzahlen, diverse Primzahltests, danach Faktorisierung. Und das für den Anfang in bc.

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

https://de.wikipedia.org/wiki/Sieb_von_Atkin

Die naivste Implementation ist ein Primzahlsieb. Da machst du eine Schleife und berechnest den Rest, der herauskommt, wenn du die Testzahl durch alle ganzen Zahlen grösser als Eins und kleiner als deine Zahl teilst und schaust, ob der Rest irgendwo darin 0 wird.

Natürlich geht es auch anders aber dieser Algorithmus basiert auf der definierenden Eigenschaft von Primzahlen, nämlich dass sie sich durch keine kleinere natürliche Zahl ohne Rest teilen lassen. Wenn man nicht an Rechenaufwand interessiert ist genügt das.

Als Teiler genügen die ungeraden Zahlen von 3 bis zur Wurzel der Testzahl...

1
@atoemlein

Bis zur Wurzel ist mir schon klar... deshalb das Adjaktiv "naivste". Habe nie bahaupted, das sei die effizienteste Methode. Und die Zahl 2 muss unbedingt getestet werden, ansonsten könnten Zahlen der Form 2^k fälschlicherweise als Primzahlen identifiziert werden. Z.B. 16 wäre nach deiner Angabe eine Primzahl.

0
@jmaz17

2 ist ja klar, und dass es keine andern geraden Primzahlen gibt, auch.

0
@jmaz17

Nee sorry habe mich in meinem Kommentar natürlich geirrt:/

0
  • 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

Was möchtest Du wissen?