発展数学 素数の性質 （講座）
§1 素数の判別
素数の定義は｛1を除く1とその数以外の約数を持たない自然数｝＝〔2つの約数を持つ自然数〕である。この素数を掛け合わせることによってすべての整数を表すことができる。すなわちある数を因数分解をする際の最小単位である。ゆえに、ある素数の倍数である限り、その数は素数ではない。これを判別するのには、2の倍数・3の倍数・5の倍数……と、素数の倍数を下の位から調べることによってわかる。この判別方法をエラトステネスのふるいという。
§２ 最大の素数
現代発見されている最大の素数は6320430桁の数である。この数は2^(20996011)-1 （＾は、累乗を表す。この場合は2の20996011乗である）という数である。この数をエラトステネスのふるいで見分けるためには2^20996010までのすべての素数についての検証をしていく必要がある。ここからわかるとおり、エラトステネスのふるいは、あまりに大きい数になると非実用的である。