判斷N是否是質數，為什麼判斷到根號N就可以了？

12-02

判斷一個自然數是否是質數，只用看從2到根號N（原諒我這麼表示）是否能整除N。但是，為什麼呢。能不能給出個詳細證明。

如果N (N&>=2)沒有小於等於根號N，大於1的約數，那麼N必然是質數。
假設N不是質數，並且不含有小於等於根號N的約數。
因為N是合數，那麼N必然可以寫成N=p*q，並且p和q大於1。根據假設，p和q都大於根號N。那麼p*q&>N，矛盾

首先，約數是成對出現的。比如24,你找到個約數3,那麼一定有個約數8,因為24/3=8。
然後，這對約數必須一個在根號n之前，一個在根號n之後。因為都在根號n之前的話，
乘積一定小於n（根號nX根號n=n），同樣，都在根號n之後的話，乘積一定大於n。
所以，如果你在根號n之前都找不到約數的話，那麼根號n之後就不會有了。

如果N是合數，有兩個因數，都比根號N大，那麼，這兩個因數的乘積，一定比兩個根號N相乘大，也就是說比N大，矛盾。

分兩塊 2——根號N, 根號（N+1）——N-1。如果在2——根號N之間有一個是N的約數，那麼N肯定是合數，如果沒有，約數在根號（N+1）——N-1之間且不在2——根號N之間的數最小也是N+1。

大於根號N的質因子給出至少一個小於根號N的質因子

放大法，