素数的验证

来源：百度知道 编辑：UC知道 时间：2024/05/19 17:41:55
谭浩强的C语言一书中写到，判断一个数N是否为素数，只要判断是否被2到N的平方根之间的整数整除就可以，请问为什么是到N的平方根就可以了呢？

若n为质数，其因子应在1到n之间(不含1和n本身)。（此区间内无n的因子，则n为质数，若存在n的因子，则因子一定成对出现：若n1和n2为两个因子，则n1*n2=n)
而n1和n2必然一个大于根号n,另一个小于根号n。
利用此，只判断一半区间就可以了。

楼上完全正确