质数的问题
最近在看基础知识点,遇到一个小练习,使用 filter
来完成1-100
里质数的筛选。
那什么是质数呢?
经过百度后:
质数(prime number)又称素数,有无限个。
质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数。
这里就可以排除掉 1
了。
现在还剩下 2-100
这99个数。
比较传统的方法就是让每个数字从1开始除到它本身,若中间没有可以整除的则是质数
,否则是合数
。但是这个做的话会很耗时间。因为如果是素数
的话循环要从2-它本身
,数字小当然看不出来,若是十几万的数呢,性能方面很耗啊。
埃拉托色尼素数筛选法
这里有个很巧妙的的素数筛选法,不需要素数
循环从2-它本身
才判断出来是素数
:
埃拉托色尼素数筛选法可以很快速的计算出1到N之间的所有素数。将n开根号,即N^0.5,去掉2到N^0.5中所有素数的倍数,剩下的数便都是素数了。
简单总结一下就是:
只要小于或等于根号N的数(1除外)不能整除N,则N一定是素数;
反过来说就是只要小于或等于根号N的数(1除外)能整除N,则N一定是合数。
代码如下:
1 | //代码复制可用 |