204. Count Primes
Easy
Count the number of prime numbers less than a non-negative number, n
.
Example 1:
Input: n = 10 Output: 4 Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
Example 2:
Input: n = 0 Output: 0
Example 3:
Input: n = 1 Output: 0
Constraints:
0 <= n <= 5 * 106
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | class Solution { public: int countPrimes(int n) { if(n==0) return 0; bool p[n]; memset(p, true, (n)*sizeof(bool)); for(int i=2; i<sqrt(n); ++i){ if(!p[i]) continue; for(int j=i; i*j<n; ++j){ p[i*j] = false; } } int ret = 0; for(int i=2; i<n; ++i){ if(p[i]) ret++; } return ret; } }; |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | class Solution { public: int countPrimes(int n) { if(n<=2) return 0; bool I[n-1];//1,2,3,4,...,n-1 memset(I,true,n-1); I[0] = false;//the first number 1 is not a prime; int count = n-2; int next_prime_index=1;//the first prime is 2 at index 1; int p, q; while(next_prime_index<n-1){ p = next_prime_index+1;//p is prime q = p;//q is multiple of p while(q+p<n){ q += p; if(I[q-1] == true){ I[q-1] = false;//q must not be a prime count--; } } next_prime_index++; while(next_prime_index<n-1 && I[next_prime_index]==false){ next_prime_index++; } } return count; } }; |
No comments:
Post a Comment