定理
自然数n≧2は√nの整数部分以下の全ての素数で割り切れなければ素数である．

証明
nの素因数が高々2個の場合, 自然数 p, q が存在して両
方とも素数かどちらかが1であり n＝pq である. ここ
で p≧q とできるから n≧q^2 ゆえ √n≧q である．
もし素数q＜pがnを割り切るならnは素数ではない. ま
た素数q＝pならnは平方数でやはり素数ではない. ゆえ
にnが√nの整数部分以下の素数qで割り切れなければq
＝1であるからn＝pは素数である.
素因数が高々3個になればn＝pqrとなる素数または1に
等しいp≧q≧rが存在してn≧r^3となるがnの3乗根は√n
以下だから√n≧rとなり素数rがnを割り切らなければr
＝1ゆえに√n≧qとなり素数qがnを割り切らなければq
＝1ゆえにn＝pは素数となる. 素因数が4個以上の場合
も同様.

証明終了