美文网首页算法&leetocode
【leetcode】计数质数 - 埃拉托斯特尼筛法

【leetcode】计数质数 - 埃拉托斯特尼筛法

作者: BzCoder | 来源:发表于2018-12-18 23:21 被阅读19次

    相关资料以及注意事项:

    算法介绍

    要得到自然数n以内的全部素数,必须把不大于根号n的所有素数的倍数剔除,剩下的就是素数。


    算法过程

       for (int i = 0; i < n; i++) {
                arr[i] = true;
            }
    
            arr[0] = false;
            int count = 0;
            int limit = (int) Math.sqrt(n);
            // 埃拉托斯特尼筛法
            for (int i = 2; i <= limit; i++) {
                if (arr[i - 1]) {
                    // 把能被整除的数字标识出来
                    for (int j = i * i; j < n; j += i) {
                        arr[j - 1] = false;
                    }
                }
            }
    
    1. 首先建立一个布尔表arr,全部标记为True,然后开始进行剔除。
    2. 只需要计算2到n的开方之内的素数即可。
    3. 假如arr标记的为素数,就开始进行剔除。
    4. j的起始点为 i * i,因为i*1 ——> i * (i -1)在之前的(i-1)*i循环里已经剔除过了。
    5. 开始剔除,因为对应的数字是大于等于1的正整数,所以标记arr[j-1]即可。同理之前判断的a[i-1]。
    6. 循环完毕后,剩下标记为True的即为素数。

    总结心得

    妙啊,真是妙啊!

    相关文章

      网友评论

        本文标题:【leetcode】计数质数 - 埃拉托斯特尼筛法

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