Leedcode2 统计素数个数(埃氏筛选法)

思想:若当前数为素数(例:2),则2*3,2*4,2*5。。。均为合数

算法:创建一个boolean数组存放全

public static int eisaifa(int n)
    {
        boolean[] prime = new boolean[n];
        int count = 0;
        for(int i = 2;i < n;i++)
        {
            if(!prime[i]) {
                count++;
                for (int j = 2 * i; j < n; j += i) { //j每次加i等价于2*i,2*i+i=3*i,......

                    prime[j] = true;
                }
            }
        }
        return count;
    }

部n个数,素数为false,合数为true

上一篇:简单数论题型


下一篇:【POJ】3006