素数を決定するアルゴリズムとしてよく知られているのが、いわゆるユークリッドふるいである。そのためには、1と0を除いたすべての数を、選んだ数まで書き出す。次のステップを繰り返す。
1. 最初の数の倍数で、まだ消されていない数をすべて消す。
2. まだ消していない数字があれば、それを繰り返す。
アルゴリズムが終了した時点で、あなたの選んだ数が消去されていなければ、それは素数であり、そうでなければ素数ではない。
Ein bekannter Algorithmus zum bestimmen einer Primzahl ist der sog. Euklidische Sieb. Dafür schreibt man alle Zahlen ohne die 1 und 0 bis zu deiner gewählten Zahl auf. Nun wiederholst du folgende Schritte.
1. Streiche alle Vielfache der ersten, nicht gestrichenen Zahl.
2. Falls noch nicht gestrichene Zahlen existieren, wiederhole.
Wenn am Ende des Algorithmus deine Zahl nicht gestrichen ist, ist sie eine Primzahl, ansonsten ist sie keine Primzahl.