Count Primes ——LeetCode

Description:
Count the number of prime numbers less than a non-negative number, n.
 
intを与えて、その質量数より小さい数を返します.
問題を解く構想:表を打つ.

public class Solution {

    

    public int countPrimes(int n) {

        int[] count = new int[n+5];

        boolean[] isPrime = new boolean[n+5];

        Arrays.fill(isPrime, true);

        isPrime[0]=false;

        isPrime[1]=false;

        for(int i=2;i<=n;i++){

            count[i]+=count[i-1];

            if(isPrime[i]){

                count[i]++;

                for(int j =i*2;j<=n;j+=i){

                    isPrime[j]=false;

                }

            }

        }

        return isPrime[n]?count[n]-1:count[n];

    }

}