Problem:
Count the number of prime numbers less than a non-negative number, n.
Idea:
Time Complexity:
O(nloglogn)
Space Complexity:
O(n)
Solution:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua class Solution { public: int countPrimes(int n) { if (n < 3) return 0; vector<unsigned char> f(n, 1); f[0] = f[1] = 0; for(long i=2;i<=sqrt(n);++i) { if(!f[i]) continue; for(long j=i*i;j<n;j+=i) f[j] = 0; } int ans = accumulate(f.begin(), f.end(), 0); return ans; } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua // Running time: 16 ms class Solution { public int countPrimes(int n) { int ans = 0; boolean[] isPrime = new boolean[n + 1]; Arrays.fill(isPrime, true); isPrime[0] = false; if (n > 0) isPrime[1] = false; for (int i = 2; i < n; ++i) { if (!isPrime[i]) continue; ++ans; for (int j = 2 * i; j < n; j += i) isPrime[j] = false; } return ans; } } |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
""" Author: Huahua Running time: 800 ms """ class Solution: def countPrimes(self, n): if n < 3: return 0 isPrime = [True] * (n + 1) isPrime[0] = False isPrime[1] = False ans = 0 for i in range(2, n): if not isPrime[i]: continue ans += 1 for j in range(2 * i, n, i): isPrime[j] = False return ans |