Count Primes

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

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

Discussion

暴力解法。给一个整数i，如果只有1和它本身是它的因子，那i就是prime，不然就是composite。

As we know the number must not be divisible by any number > n / 2, we can immediately cut the total iterations half by dividing only up to n / 2.

Solution

//O(n^1.5) rum time
//O(1) space
public int countPrimes(int n) {
   int count = 0;
   for (int i = 1; i < n; i++) {
      if (isPrime(i)) count++;
   }
   return count;
}

private boolean isPrime(int num) {
   if (num <= 1) return false;
   // Loop's ending condition is i * i <= num instead of i <= sqrt(num)
   // to avoid repeatedly calling an expensive function sqrt().
   for (int i = 2; i * i <= num; i++) {
      if (num % i == 0) return false;
   }
   return true;
}

Follow up

Sieve of Eratosthenes算法。对每一个prime，标记它所有的倍数为composite，剩下的就都是prime了。第一层循环遍历小于n的每一个数，第二层循环做标记。

class Solution {
public:
    int countPrimes(int n) {
        int cnt = 0;
        vector<bool> isPrime(n, true);
        for(int i=2; i*i<=n; i++) {//i*i < n就可以了，后面的在访问之前会标记的
            if(isPrime[i]) {
                //1. j start from i*i, because even i*(i-1) has been marked off by multiple of i-1
                //2. j+=i, making sure it's in increments of i
                for(int j=i*i; j<n; j+=i) {
                    isPrime[j] = false;
                }
            }
        }
        //count
        for(int i=2; i<n; i++) {
            if(isPrime[i]) cnt++;
        }
        return cnt;
    }
};

bool *isPrime = new bool[n]; 取代vector速度会快好多。

Computational complexity of the algorithm is O(nlog(log(n))). Strong proof of this fact is not too complex and based on several approximations from the prime numbers' theory. It can be found in [1]. The space complexity is O(n).

Follow up

如果问题是：在小于n的数中，Count the number of prime numbers 和能分解成两个prime乘积的数.
那就从所有的prime中取出任意两个，如果乘积小于n，那就算上。

int countPrimes2(int n) {
     int cnt = 0;
     vector<bool> isPrime(n, true);
     for (int i = 2; i*i <= n; i++) {//i*i < n就可以了，后面的在访问之前会标记的
         if (isPrime[i]) {
             //1. j start from i*i, because even i*(i-1) has been marked off by multiple of i-1
             //2. j+=i, making sure it's in increments of i
             for (int j = i*i; j<n; j += i) {
                 isPrime[j] = false;
             }             
         }
     }
     //count prime
     for (int i = 2; i<n; i++) {
         if (isPrime[i]) cnt++;
     }
     //count the composites that can be prime factorized with i and some other prime
     for (int i = 2; i < n; i++) {
         if (isPrime[i] == false) continue;
         for (int j = i; j < n; j++) {//j starts from i, not i+1
             if (isPrime[j] == false) continue;
             if (i*j < n) {
                 cnt++;
             }
         }
     }
     return cnt;
 }