[このファイルの頭へ]簡単である。自然数 N が、それより小さい数で割り切れなければ、N は素数である（もちろん、1 と N 自身は考慮に入れない）。例えば、7 を考えてみる。これは、2, 3, 4, 5, 6 のいずれでも割り切れない。つまり、7 は素数だということである。
これが、 N が素数かどうかを判断する「最も単純で簡単な」方法だ（事実上、N の素因数を見つける「唯一の」方法である。他の方法も、このやり方を改良したものに過ぎない）。
しかし、これには長い長い時間がかかる。N より小さい全ての数で割る必要はないんじゃないか、それより小さい素数で割ってみるだけでいいんじゃないか、とあなたは思うかもしれない。
その通りである。これで時間が節約できる。2 を試した後で、4, 6, 8 などで割ってみるのはバカげている（3 の後で 6, 9, 12 などを、5 の後で 10, 15, 20 などを試すのも同様）。N を 101 としよう。この場合、2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ... 89, 97 で割ってみるだけでいい（99個の代わりに25個、約4分の1。どれでも割り切れないので、101 は素数である）。
あなたはさらに思うであろう、どうして「N より小さい素数」なのか？ 「N の平方根より小さい素数」でいいじゃないか。
またしても、その通り。101 の平方根は 10.5 だから、N は 2, 3, 5, 7 で割ってやるだけでいい。たったの4回だ。説明した方がいいかな？ もし N が素数x と素数y とに割り切れる（つまり N=xy）とすると、x と y のいずれかは N の平方根よりも小さくなければならない。もし x と y の両方ともが N の平方根よりも大きいとすると、xy（=N）は N よりも大きいということになり、これは不条理である。したがって、もし N が素数でないとすると、N は「N の平方根よりも小さい素数」で割り切れる。
平均すると、任意の連続した100個の自然数の中には、6.87個の素数がある（参照：エミール・ボレル『素数』芹沢正三訳、文庫クセジュ、1959年）。10000000000（10の10乗）以下には、455052511個の素数がある。N を 10の20乗とする。N の平方根は、10000000000（10の10乗）で、そのうちの455052511個が素数である（つまり、N+1 が素数かどうか判断するには、運が悪ければ、455052511回試さねばならないということ）。
N を10の155乗（RSA暗号方式の鍵のサイズ）とすると、最悪で、10の76乗回試さなければならない。
ところで、N が素数かどうかを判断するだけなら（N の素因数を求めるという問題はさておき）、もっと素早く解ける。
2 の（N-1）乗を求め、それを N で割る。余りが 1 でないならば、N は素数ではない。14 で試してみよう。2 の（14-1）乗は、8192 である。8192 を 14 で割ると、余りは 2。よって、14 は素数ではない。
余りが 1 の時、N は必ずしも素数であるとは限らないが、ほとんどの場合、素数であろうと推定できる（例外は100万にひとつ）。余りが 1 であるものだけを、それが本当に素数であるかどうかチェックすればよい。
もしあなたが Mac ユーザーなら、AppleScript か HyperCard が助けてくれるだろう。HyperCard に「answer 2^(N-1) mod N」と頼んでみて、答えが「1」ならば、N はほぼ素数である（N が16400以下なら、このやり方が通用する）。