题目详情

统计n以内的素数个数
素数：只能被1和自身整除的自然数，0，1除外

输入：100，输出：25
重点考察：埃筛法

Java代码（暴力算法）

public class Solution {
    public int countPrimes(int n) {       
           int count = 0;
           for(int i = 2; i<n: i++){
                //只要是素数count++
                coutn += isPrime(i) ? 1:0;
           }
            return count;

    }
    private int isPrime(int x){
        //只要到根号x就可以停
        for(int i = 2; i * i <= x ; i++){
            if(x % i == 0){
                return 0;
            }
        }
        return 1;
    }
}

Java代码（埃筛法）

素数 非素数（合数）12 = 2 * 6其中2和6称为12的因子，其中两个素数的积为合数

所以我们在每次迭代可以用当前数字筛选出一定为合数的数字，并标记合数，这样只需要判断数组中false的个数就可以判断有多少素数

public class Solution {
    public int countPrimes(int n) {       
        boolean[] isPrime = new boolean[n]; //false代表素数
        int count = 0;
        for(int i = 2 ; i < n; i++){
            if(!isPrime[i]){
                count++;
                for(int j = i * i;j < n; j+=i){
                    isPrime[j] = true;
                }
            }
        } 
        return count;
    }
}