美文网首页井英俱乐部
埃拉托斯特尼素数筛选法

埃拉托斯特尼素数筛选法

作者: 沛文沛语 | 来源:发表于2019-05-30 21:31 被阅读6次
    埃拉托斯特尼素数筛选法

    素数的定义:大于1的自然数中,除了1和该数自身外,无法被其他自然数整除的数称为 素数(Prime Number),比如2、3、5、7、11

    如何发现素数

    常见的方法就是一个个的尝试计算。上图中这个方法的巧妙之处在于,给定一个范围的数值,先用最小的一个数值2去做因子,排除所有的偶数。然后再用3去做因子,再去排除一部分。

    这样后面的已经被排除的数字就不再参与运算了,大大降低了整个计算的复杂度,少做了很多无用功,也就大大提高了运算的速度。

    相关文章

      网友评论

        本文标题:埃拉托斯特尼素数筛选法

        本文链接:https://www.haomeiwen.com/subject/waunzqtx.html