判断一个数是否为素数的算法

Question

判断一个数n是不是素数，我只知道有这个方法：让n除以2到n的平方根之间的每一个数，如果n能被2到n的平方根之间的某个数整除，则说明n不是素数，否则n一定是素数。（n大于2）
但是我在一个程序上又看到了另一种算法，就是让n除以2到n/2之间的每一个数，如果都除不尽，那这个数就是素数。
原先那个方法我知道是什么思路的，可是这个方法……是什么原因呢？为什么是除以2到n/2呢？

Answer 1

找质数的方法：写出这个数的因数。再判断这个数是质数还是合数。
1、一个数除了1和本身，不再有别的约数，这样的数叫做质数或者素数。例如：2，3，5，7，11，13，17，19，23，29等等。
2、一个数，除了1和本身，还的别的因数，这样的数叫做合数。例如4、8、8、9等等。例如：2的所有因数是1和2两个，所以2是质数。例如6的所有因数是：1，2，3，6。一共是4个，所以6是合数。

找因12的因数：
1×12=12 2×6=12 3×4=12 所以12的因数有：1，2，3，4，6，12。共6个。
找因数的方法可以把这个数分成两个因数相乘的积。从一开始比较容易找，写的时候最好能从小到大写出来。重复的只能写一个。例如9的因数：1×9=9 3×3=9 9的因数是：1，3，9共3个。（重复的3只能写一个。）

Answer 2

因为没必要去比较大于n/2的情况，因为n=2*n/2，假设m>n/2，那么n必然不能被m整除，就好像100=2*50，不需要再去比较51,52....本回答被提问者和网友采纳