如何快速分辨一大数是质数还是合数

投稿:拥之则安 优质问答领域创作者 发布时间:2024-01-13 08:48:35
如何快速分辨一大数是质数还是合数

判断一个较大的整数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.