计算质数

问题陈述

统计所有小于非负整数 n 的质数的数量。

思路分析

质数：除了1和本身之外，没有别的因数。因此可以对1<i<n, 判断s%i==0？

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int countPrimes(int n) {
    if (n <= 2) return 0;
    boolean[] primes = new boolean[n];  //创建整个素数数组
    Arrays.fill(primes, true);      //初始化全部为素数
    primes[0] = false;
    primes[1] = false;                  //划掉0和1
    int sqrt = (int)Math.sqrt(n);       //设置上界
    for (int i = 2; i <= sqrt; i++) {
        if (!primes[i]) continue;       //不是素数，可以跳过
        for (int multi = i*i; multi < n ; multi += i){
            primes[multi] = false;      //划掉倍数
        }
    }
    int count = 0;
    for (boolean prime : primes) {      //统计数组中素数的数量
        if (prime) count++;
    }
    return count;
}