素数とは、
約数が1とその数自身しか約数を持たない自然数を素数という。即ち、約数が2個しか持たない数である。
たとえば、２の約数は1と2で約数は2個であるから素数、4の約数は1、2、4で約数は3個であるから素数でない。
最初の素数は2ではじまり3、5、7、11、13、17、19、23、29、…、と続き一億に近い素数は99999989で5761455 番目である。
「エラトステネスのふるい」は素数を求める方法としては非常に単純な方法である。約数を求める他の方法と違って 、倍数を順次消していく方法である。たとえば、100までの素数を求めるには、
・初めに、100までの数字の列を書く(2，3，4，5，6，7，8，9，10，11，12，13，14，15，16，…，99,100)
・次に、数字列の初めの数(2)の倍数を消す。(2，3，・，5，・，7，・，9，・，11，・，13，・，15，・，…，99,・)
・同様に、まだ消されていない数(３)の倍数を消す。(2，3，・，5，・，7，・，・，・，11，・，13，・，・，・，…，・,・)
同様にして、消されていない数の倍数を順次消していき。最後に残った数が素数となる。