Force buckle 204 Count prime

subject

Given integer n , return All integers less than nonnegative n The number of prime numbers .

Example

Input ：n = 10
Output ：4
explain ： Less than 10 There are a total of 4 individual , They are 2, 3, 5, 7 .

Input ：n = 0
Output ：0

Input ：n = 1
Output ：0

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/count-primes
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Method 1： Ethmoid

Java Realization

class Solution {
    
    public int countPrimes(int n) {
    
        int[] isPrime = new int[n];
        Arrays.fill(isPrime, 1);
        int ans = 0;
        for (int i = 2; i < n; i++) {
    
            if (isPrime[i] == 1) {
    
                ans++;
                if ((long) i * i < n) {
    
                    for (int j = i * i; j < n; j += i) {
    
                        isPrime[j] = 0;
                    }
                }
            }
        }
        return ans;
    }
}