判断一个数是不是素数

比方 100: 10*10; 这里根号下N 根号下100 为 10。 只要 1 到 10 都除不尽 100 那麼 100 是素数
100= 1*100, 2*50, 4*25, 5*20, 10*10, 20*5, 25*4, 50*2, 100*1
如果 拿 1 到 100 的数都去除 100，是否一半的情况重复 事倍而功半呢?
希望对你的理解有所裨益

1.
用反证法。
假设N存在一个因数a,而且a>√N。则a*√N>N。
N的所有质因数的乘积不可能大于N，矛盾。
证毕

2.
用归纳法。
n=a*b,不考虑最坏情况，则a,b之中一定有一数小于√N
考虑最坏情况a=b=√N，则只需判断到√N
根据归纳法，此题得证。

对于一个确定是数N，不管是素数还是合数，比√N大且比N小的数肯定不是N的约数了，你判断N是不是素数，主要就是找N是不是有大于1小于N的约数么，所以不需要这么大的范围。

比方 100: 10*10; 这里根号下N 根号下100 为 10。 只要 1 到 10 都除不尽 100 那麼 100 就是素数
100= 1*100, 2*50, 4*25, 5*20, 10*10, 20*5, 25*4, 50*2, 100*1
如果 拿 1 到 100 的数都去除 100，是否一半的情况重复 事倍而功半呢?