204.计数质数

解题思路：埃氏筛

基于这样的事实：如果 x 是质数，那么大于 x 的 x 的倍数 2x,3x,… 一定不是质数，因此我们可以从这里入手。
我们设 isPrime[i] 表示数 i 是不是质数，如果是质数则为 true，否则为 false。
从小到大遍历每个数，如果这个数为质数，则将其所有的倍数都标记为合数（除了该质数本身），
即 false，这样在运行结束的时候我们即能知道质数的个数

package leadcode;

import java.util.Arrays;

/**
 * @author : icehill
 * @description : 计数质数
 * 统计所有小于非负整数 n 的质数的数量。
 * 示例 1：
 * 输入：n = 10
 * 输出：4
 * 解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
 * 示例 2：
 * 输入：n = 0
 * 输出：0
 * 示例 3：
 * 输入：n = 1
 * 输出：0
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/count-primes
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 解法1：枚举（类似暴力做法，只不过优化了计算质数的时间复杂度）
 * 时间复杂度：O(n*sqrt(n)) 空间复杂度：O(1)
 * 解法2：埃氏筛（官方叫法）
 * 基于这样的事实：如果 x 是质数，那么大于 x 的 x 的倍数 2x,3x,… 一定不是质数，因此我们可以从这里入手。
 * 我们设 isPrime[i] 表示数 i 是不是质数，如果是质数则为 true，否则为 false。
 * 从小到大遍历每个数，如果这个数为质数，则将其所有的倍数都标记为合数（除了该质数本身），
 * 即 false，这样在运行结束的时候我们即能知道质数的个数
 * @date : 2021-05-02
 */
public class Solution204 {
    public static void main(String[] args) {
        Solution204 solution204 = new Solution204();
        System.out.println(solution204.countPrimes(2));
        System.out.println(solution204.countPrimes(4));
        System.out.println(solution204.countPrimes(5000000));
    }

    /**
     * 解法2，埃氏筛
     *
     * @param n
     * @return
     */
    public int countPrimes(int n) {
        boolean[] isPrimes = new boolean[n];
        //初始化全部设置true，代表质数
        Arrays.fill(isPrimes, true);
        int count = 0;
        for (int i = 2; i < n; i++) {
            //如果是质数，则count+1，并且把质数的所有倍数设置为false
            if (isPrimes[i]) {
                count++;
                for (int j = 2 * i; j < n; j = j + i) {
                    isPrimes[j] = false;
                }
            }
        }
        return count;
    }

    /**
     * 解法1：枚举
     *
     * @param n
     * @return
     */
    public int countPrimesTwo(int n) {
        int count = 0;
        //0 1既不是质数也不是合数
        for (int i = 2; i < n; i++) {
            if (isPrime(i)) {
                count++;
            }
        }
        return count;
    }

    /**
     * 判断一个数是否为质数
     * 计算质数，本来应该是计算i~x-1是否能被x整除
     * 反过来想，如果x=y1*y2（y1<=y2），那么判断（x%y1==0)跟（x%y2==0)作用其实一样，
     * 如果我们每次只取y1(小的那个数)，那就是sqrt(x)>=y1*y2>=y1^y1，
     * 所以只需要判断【2，sqrt(x)】这个区间即可
     *
     * @param x
     * @return
     */
    boolean isPrime(int x) {
        for (int i = 2; i * i <= x; i++) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }
}