LeetCode [204] Count Primes

 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; } };