题目：
Description:
Count the number of prime numbers less than a non-negative number, n.
Credits:
Special thanks to for adding this problem and creating all test cases.
链接：
题解：
求小于n素数。正好前几天PKU的Java课上讲到埃式筛法，一下就想到了它。先建立一个数组，假定所有大于1小于n的数都mark为素数。之后从第一个素数2开始，mark这个素数的倍数为非素数。注意边界。时间复杂度等于(n/2+n/3+n/5...+n/比n小的最大素数） = n*(小于n的所有素数倒数的和） = O(n * log(logn))
Time Complexity - O(nloglogn)， Space Complexity - O(n)。
public class Solution { public int countPrimes(int n) { if(n < 2) return 0; boolean[] dp = new boolean[n]; Arrays.fill(dp, 2, n, true); int result = n - 2; for(int i = 2; i * i < n; i++){ if(dp[i]){ //if i is a prime for(int j = i; i * j < n; j++){ if(dp[i * j]){ //then i * j is not a prime, set dp[i * j] to false dp[i * j] = false; result--; } } } } return result; }}
Update:
注意Arrays.fill假如给定start index和end index的话是前闭后开区间。
sieve of eratosthenes
public class Solution { public int countPrimes(int n) { if(n < 2) return 0; boolean[] isPrime = new boolean[n]; Arrays.fill(isPrime, 2, n, true); int result = n - 2; for(int i = 2; i * i < n; i++) { if(isPrime[i]) { for(int j = i; i * j < n; j++) { if(isPrime[i * j]) { isPrime[i * j] = false; result--; } } } } return result; }}
二刷：
依然使用 Sieve of Eratosthenes。要注意题目说的是比n小的质数，所以我们只需要建立一个size n的数组就可以了。
Java:
Time Complexity - O(nloglogn)， Space Complexity - O(n)
public class Solution { public int countPrimes(int n) { if (n < 3) { return 0; } boolean[] isPrime = new boolean[n]; Arrays.fill(isPrime, 2, n, true); int res = n - 2; // no 0 and 1 for (int i = 2; i * i < n; i++) { if (isPrime[i]) { for (int j = i; j * i < n; j++) { if (isPrime[i * j]) { isPrime[i * j] = false; res--; } } } } return res; }}
三刷:
Java:
public class Solution { public int countPrimes(int n) { if (n < 3) return 0; boolean[] nums = new boolean[n]; Arrays.fill(nums, 2, n, true); int count = n - 2; for (int i = 2; i * i < n; i++) { if (nums[i]) { for (int j = i; i * j < n; j++) { if (nums[i * j]) { nums[i * j] = false; count--; } } } } return count; }}
Reference:
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
https://leetcode.com/discuss/81779/12-ms-java-solution-modified-from-the-hint-method-beats-99-95%25