|
质数（prime number）又称素数，有无限个。 质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。 在OI竞赛中，需要判断一个数是否为质数的情况很常见，那么如何才能更好的来判断呢？ 首先我们就从质数的定义入手吧，那么判断的区间就应该在（1，n）开区间中所有的自然数。 接下来重点来了，我们要让缩小判断的范围，让程序的运算更快一些。 对任意合数n，根据定义可以设n=p*q(p<=q)则p<=根号n，从而若n>1且不是素数，则它的最小素因子一定不超过p,从而不超过根号n。 所以判断的范围缩小到了（1，根号n] 左开右闭区间中所有的自然数。 这样就成功的将复杂度从O(n)降到了O(根号n)。 这样就可以了吗？我们再来看一遍定义，质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。 好了到这里就是网络上大部分出现的质数判断的方法了。 但是在这里小编还想继续优化一下。如果一个数是大于1的偶数那么它一定被2整除，也肯定不是质数。那对于基数来说，自然不需要再判断所有的偶数是否可以整除了。 这样循环变量每次自增2，把运行次数又缩短到了原来的一半。 到这为止，是目前小编能力以内能想到最优的解法了，如果你还有什么更好的解法，随时欢迎大家和我交流。   |
|
|
