wie findet man heraus welche und wie viele Teiler man brauch um zu prüfen ob eine Zahl Prim oder Nicht-Prim ist?

Question

Aufgabe:

wie findet man heraus welche und wie viele Teiler man brauch um zu prüfen ob eine Zahl Prim oder Nicht-Prim ist?

Problem/Ansatz:

Da eine Zahl x_n gebildet werden kann durch x • x gilt für jedes x_{n ,}dass nur die Anzahl von den natürlichen Zahlen 1 bis √x_n benötigt werden um zu prüfen ob eine Zahl x_n Prim oder Nicht-Prim ist.

Kann, das jemand bestätigen?

Comments

Selbstverständlich.

Wen a*b=x gilt und einer der beiden Faktoren größer als √x ist, ist der andere Faktor kleiner als √x.

---

welche (...) Teiler man brauch(t)

Ich würde als Teiler 2 und dann die ungeraden natürlichen Zahlen in aufsteigender Reihenfolge nehmen, dann kommt man wenn nicht-prim rascher auf eine Teilbarkeit (ganzzahlig ohne Rest) als bei absteigender Reihenfolge.

... gebildet werden kann durch x • x

Schreibe stattdessen "gebildet werden kann durch a • b" weil sonst hast Du ein bisschen viele Zahlen als x benannt.

Answer 1

Ein naiver Ansatz zur Teilerfindung prüft alle Zahlen bis √x_n. Optimiert man diesen Algorithmus, indem man nach der Prüfung von 2 und 3 nur noch Zahlen der Form 6k ± 1 testet, sinkt der Rechenaufwand auf ein Drittel. Sollen viele oder sehr große Zahlen x_n faktorisiert werden, ist es performanter, zu prüfende Primzahlen vorher mit dem Sieb des Eratosthenes oder Atkin zu berechnen.

Ich habe schon ein paar Programmieraufgaben zur Primfaktorzerlegung bei projecteuler.net gemacht und das klappt damit eigentlich recht gut.

Wir haben aber hier in der Mathelounge den Benutzer HyperG, der sich damit aber noch besser auskennt und dir für spezielle Zahlen auch erstmal einen anderen Primzahltest vorschlagen kann. Das hängt immer auch davon ab, wie groß deine Zahl xn ist, die du prüfen möchtest. Es gibt Zahlen mit 270 Ziffern, die bis heute noch nicht faktorisiert worden sind, und dabei klingen 270 Ziffern doch gar nicht so viel.