百度&必应权4, 日IP8000. 查看详情
自助收录

使用埃筛法解决“统计素数个数”问题

算法刷题2年前 (2023)更新 江南白衣
263 0 0
使用埃筛法解决“统计素数个数”问题

题目:统计N以内的素数
素数:只能被1和自身整除的数,0、1除外

解法2:埃氏筛
利用合数的概念(非素数),素数 * N必然是合数,因此可以从2开始遍历,将所有的合数做上标记。

将合数标记为true,j = i * i 从 2 * i 优化而来,系数2会随着遍历递增(j += i,相当于递增了系数2),
每一个合数都会有两个比本身要小的因子(0,1除外),2 * i 必然会遍历到这两个因子
当2递增到大于根号n时,其实后面的已经无需再判断(或者只需判断后面一段),而2到根号n、实际
上在 i 递增的过程中已经计算过了,i 实际上就相当于根号n
例如:n = 25 会计算以下
2 * 4 = 8
3 * 4 = 12
但实际上8和12已经标记过,在n = 17时已经计算了 3 * 4,2 * 4

package od;

/**
 * 埃氏筛选法统计素数个数
 * 利用合数的概念(非素数),素数*n必然是合数,因此可以从2开始遍历,将所有的合数做上标记
 * 原文地址:https://www.codernav.com/2786.html
 */
public class Odtest07 {
    public static void main(String[] args) {
        int count = eratosthenes(100);
        System.out.println(count);
    }

    public static int eratosthenes(int n) {
        boolean[] isPrime = new boolean[n];//false代表素数
        int ans = 0;
        for (int i = 2; i < n; i++) {
            if (!isPrime[i]) {
                ans += 1;
                for (int j = i * i; j < n; j += i) {//j就是合数的标记位
                    isPrime[j] = true;
                }
            }
        }
        return ans;
    }
}

 

© 版权声明

相关文章

暂无评论

暂无评论...