判断一个较大的整数N是不是质数,其做法是:找到两个连续的质数a,b(a<b),使得N最接近于ab,且N<ab,然后一一验证N是否能被所有小于a的质数整除即可。
显然,对于较大的整数N,要找到两个连续的质数a、b,使得N<ab还是有点困难和麻烦的。注意到a<b,而a、b是连续的质数,所以 a^2<N<ab,即a<√N<√ab,
所以可用[√N]([√N]表示不超过√N的最大整数)替代a。
例如,判断2011是质数还是合数?
因为[√2011]=44,所以要判断2011是不是质数,只需要验证2011能否被小于44的某个质数整除就可以了,完全没必要验证到2011.