統計所有小于非負整數 n 的質數的數量。

示例 1：

輸入：n = 10
輸出：4
解釋：小于 10 的質數一共有 4 個, 它們是 2, 3, 5, 7 。

解題思路

大于等于5的質數一定和6的倍數相鄰。例如5和7，11和13,17和19等等；

證明：令x≥1，將大于等于5的自然數表示如下：

··· 6x-1，6x，6x+1，6x+2，6x+3，6x+4，6x+5，6(x+1），6(x+1)+1 ···

可以看到，不和6的倍數相鄰的數為6x+2，6x+3，6x+4，由于2(3x+1)，3(2x+1)，2(3x+2)，所以它們一定不是素數，再除去6x本身，顯然，素數要出現只可能出現在6x的相鄰兩側。因此在5到sqrt(n)中每6個數只判斷2個，時間復雜度O(sqrt(n)/3)。

代碼

class Solution {public int countPrimes(int n) {int res=0;for(int i=2;i<n;i++)res+=isPrimes(i);return res;}public int isPrimes(int n) {double nSqrt;if(n==2||n==3) return 1;if(n%6!=1&&n%6!=5) return 0;nSqrt= Math.floor(Math.sqrt((double)n));for(int i=5;i<=nSqrt;i+=6)if(n%i==0||n%(i+2)==0) return 0;return 1;}
}