素数は、1よりも大きく、1でのみ分割され、分割される自然数です。少数では、あらゆる種類の除数を試すだけです。整数のすべての整数結果も仕切りであるため、2からルート、テストする数を含むすべての総数を試してみる必要があります。


Siebenメソッドは、小さなnのすべてのプライムナンバーを見つけるためにやや洗練されています：

 - エラトステネスのふるい：これは、プライムナンバーのみが残るまで、5などのすべての素数を決定する最も単純なアルゴリズムの1つです。
 - アトキンによるふるい：これは、nのすべてのプライムナンバーを決定するための別の画面プロセスです。それは、各素数が特定の残留クラスモジュロ60を持ち、この事実を使用して素数をフィルタリングするという事実に基づいています。


最新の方法は非常に多数に使用されます：

-miller-rabinテスト：これは、数字をプライム番号として識別する確率的テストです。画面メソッドよりも速いですが、複合番号が素数として識別される可能性は少しあります。
-AKS-E-Empasionテスト：これは、数値がプライム番号であるかどうかを判断するために多項式時間に機能する決定論的アルゴリズムです。これは、プライム決済の最も既知のアルゴリズムですが、その複雑さのために、比較的少ない数にしか使用できません。
Eine Primzahl ist eine natürliche Zahl, die größer als 1 ist und nur durch 1 und sich selbst teilbar ist. Bei kleinen Zahlen kann man einfach alle möglichen Teiler durchprobieren. Da jedes ganzzahlige Ergebnis eines ganzzahligen Teilers auch wieder ein Teiler ist, muss man maximal alle ganzen Zahlen von 2 bis einschließlich der Wurzel, der zu testenden Zahl, ausprobieren.


Etwas raffiniertere Methoden zum finden aller Primzahlen kleiner n sind Siebverfahren:

- Sieb des Eratosthenes: Dies ist einer der einfachsten Algorithmen zur Bestimmung aller Primzahlen kleiner n. Es geht wie folgt: Man erstellt eine Liste aller Zahlen von 2 bis n, und streicht dann alle Vielfachen von 2, alle Vielfachen von 3, alle Vielfachen von 5 usw., bis man am Ende nur noch die Primzahlen übrig hat.
- Sieb von Atkin: Dies ist ein weiteres Siebverfahren zur Bestimmung aller Primzahlen kleiner n. Es ist schneller als das Sieb des Eratosthenes, aber auch etwas komplexer. Es beruht auf der Tatsache, dass jede Primzahl eine bestimmte Restklasse modulo 60 hat, und nutzt diese Tatsache aus, um Primzahlen zu filtern.


Für extrem große Zahlen werden modernere Verfahren verwendet:

- Miller-Rabin-Test: Dies ist ein probabilistischer Test, der eine Zahl als wahrscheinliche Primzahl identifiziert. Es ist schneller als die Siebverfahren, aber es gibt eine kleine Wahrscheinlichkeit, dass eine zusammengesetzte Zahl als Primzahl identifiziert wird.
- AKS-Primzahltest: Dies ist ein deterministischer Algorithmus, der in Polynomialzeit arbeitet, um zu entscheiden, ob eine Zahl eine Primzahl ist oder nicht. Es ist der schnellste bekannte Algorithmus zur Primzahltestung, aber aufgrund seiner Komplexität ist er nur für relativ kleine Zahlen praktisch anwendbar.