Count Primes

https://leetcode.com/problems/count-primes/description/

Description:

Count the number of prime numbers less than a non-negative number,n.

Thoughts

统计n以前的质数数字。Sieve of Eratosthenes。用一个长度为n的数组对应0~n - 1，把其中不是prime的标出来。第一个prime是2，把能2的倍数全部在数组中标出来，即2*2， 2*3。。。直到2*j >= n.然后i++ 移到下一个没被标记的prime, 即3，同理。直到i移到sqrt(n)为止, 因为大于sqrt(n)的j乘以i会超出n。

Code

/*
 * @lc app=leetcode id=204 lang=cpp
 *
 * [204] Count Primes
 */

// @lc code=start
class Solution {
public:
    int countPrimes(int n) {
         vector<bool> prims(n, true);
         for (int i = 2; i < sqrt(n); ++i) {
             if (!prims[i]) continue;
             for (int j = 2; i * j < n; ++j) {
                 prims[i * j] = false;
             }
         }
         int res = 0;
         for (int i = 2; i < n; ++i) {
             if (prims[i]) {
                 ++res;
             }
         }
         return res;
    }
};
// @lc code=end

Analysis

Errors:

1. 用的是把prime存下来，判断i是否能和每个prime相%==0. TLE。除非加入判断是否超过square的语句:

for(int j=0;j<primes.size();j++){
if(primes.get(j)*primes.get(j)>i) break;

时间复杂度计算过于复杂，空间O(n).