204. Count Primes

题目：

Description:

Count the number of prime numbers less than a non-negative number, n.

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

Show Hint

Hide Tags

Hash Table Math

链接： http://leetcode.com/problems/count-primes/

2/23/2017

一定要看清题目，这里需要小于n的质数的数目。

选择下标时一定要清楚此下标的数组值代表什么，实在麻烦的话就选择最基本的，比如此处isPrime[i]就代表i是否是质数，通过后面的运算得到小于n的所有。

 1 public class Solution {
 2     public int countPrimes(int n) {
 3         if (n < 2) return 0;
 4 
 5         boolean[] isPrime = new boolean[n + 1];
 6         for (int i = 0; i <= n; i++) isPrime[i] = true;
 7         isPrime[0] = false;
 8         isPrime[1] = false;
 9         int count = 0;
10 
11         for (int i = 2; i <= n / i; i++) {
12             for (int j = i; j <= n / i; j++) {
13                 isPrime[i * j] = false;
14             }
15         }
16 
17         for (int i = 0; i < n; i++) {
18             if (isPrime[i]) count++;
19         }
20         return count;     
21     }
22 }

还可以用Arrays.fill(isPrime, 2, n, true);是个巧妙的方法