16/05/30 00:26:43.63 BL4+K78F.net
nを2以上として…
nが素数でないとすると n=a*b (aとbは2以上)と書ける
aとbがともに√nよりも大きいと仮定すると積a*bはnよりも大きいことになり矛盾
よってaとbの少なくとも一方は√n以下である
したがって、nが素数でないとすると、nは2以上√n以下のある数で割り切れる
言い換えれば、2以上√n以下のどの数でも割り切れないならばnは素数である
また、2以上√n以下のある数で割り切れるならば n=a*b (aとbは2以上)と書けるので、nは素数でない
つまり、2以上√n以下の数で割り切れるかどうかにより、素数かどうかを判定できる