Probedivision - DDDEasy

Die Probedivision ist ein Algorithmus aus dem mathematischen Teilgebiet der Zahlentheorie. Der Algorithmus ermittelt einen nichttrivialen Teiler einer positiven ganzen Zahl, wenn einer existiert. Findet er keinen solchen Teiler, so ist die vorgegebene Zahl eine Primzahl. Die Probedivision ist somit sowohl ein Faktorisierungsverfahren als auch ein Primzahltest. Führt man die Probedivision weiter, nachdem ein nichttrivaler Teiler gefunden wurde, so kann man letztendlich die Primfaktorzerlegung einer natürlichen Zahl ermitteln. In der Regel benutzt man dieses Verfahren nur als Faktorisierungsverfahren, um Primfaktoren bis zu einer gewissen Schranke zu finden. Man spricht dann von unvollständiger Probedivision. Mehr lesen