判断素数的算法的说明
给定一个整数x,判断x是否为素数。算法基本思路如下:让x被2到sqrt(x)除,如果x能被2至sqrt(x)之中任何一个整数整除,那么说明x不是质数,否则是质数。
c语言代码如下:
#include <cmath>
bool IsPrime(int x)
{
for(int i = 2; i <= (int)sqrt(x); i++)
{
if((x % i) == 0)
return false;
}
return true;
}
为什么说“如果x能被2至sqrt(x)之中任何一个整数整除,那么说明x不是质数,否则是质数。”
这个问题归结于这样的命题:
正整数x,设Q=sqrt(x)
1、如果存在一个大于1小于Q的整数可以整除x,则必然存在一个大于Q小于x的整数可以整除x;
2、如果不存在一个大于1小于Q的整数可以整除x,则必然也不存在一个大于Q小于x的整数可以整除x。
先证明第1条
设B是一个整数,1 < B < Q,且B可以整除x。按整除的定义存在一个整数C,使得 B * C = x,必然有C > Q,因为如果C <= Q,则B * C <= B * Q < Q * Q = x。这与B * C = x相矛盾。
再证明第2条
设C是一个整数,Q < C < x,且C可以整除x。按整除的定义存在一个整数B,使得 B * C = x,必然有B < Q,因为如果B >= Q,则B * C >= Q * C > Q * Q = x。这与B * C = x相矛盾。
证毕。