素数的判别

昨天在学C语言循环结构的时候，一个经典题目，输入一个数字m，判别它是不是素数。

根据素数的定义，除了它本身以及1之外，不能被第三个整数整除，那么就是素数。

于是很自然的循环就来了，从2除到m-1，都不能整除，就判定是素数。

这样子当然没有问题，大多数人都想得到这样子去操作，但是实际上从2除到sqrt（m）就可以了。

这样子一下子在时间复杂度上就省了很多，比如输入一个10000，本来要循环10000次，现在只需要循环100次了，足足节省了100倍的时间。算法的优劣感由此可见一斑。

为什么从2除到sqrt（m）就可以了呢。

这里可以用反证法：

假设2到k=sqrt(m)，都没整除，却有一个整数s>k，可以整除m，商m/s，m也是可以整除这个商的；

则m/s ∈（2，k）,这是必然的，不然，s>k且m/s>k,那么s*m/s=m>k*k=m,就不对了；

这又与一开始的假设矛盾。