LeetCodeDay26 —— 计数质数

204. 计数质数

描述

• 统计所有小于非负数整数 n 的质数的数量。

示例

  输入: 10
  输出: 4
  解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

思路

1. 一次判断从2~n质数的数量返回，核心算法转换为判断一个数是否为质数。
2. 根据质数的字面定义，一个数只能被1和自身整除即为质数，可以2~m-1依次求余，为0则不为质数。
3. 优化点：可以不必从2~m-1，只需遍历2 ~ √m.因为如果m能被2 ~ m-1之间任一整数整除，其二个因子必定有一个小于或等于√m，另一个大于或等于√m。例如16能被2,4,8整除，16=28,2小于4,8大于4，16=44,4=√16，因此只需判定在2~4之间有无因子即可。
4. 上述方案实现正确，但是超过了预期时间。简单估算一下，大约是O(n*n)级别的复杂度。优化方向是利用空间换时间，维持一个大小为n的bool型数组，当x判断完毕后，把数组内所有x的倍数都置位false，每次判断一个数是否为质数时先查表，表里面有才遍历。
5. 最优解：埃拉托斯特尼筛法(参考)

- 一个数如果在遍历到它的时候都没有被标记，则证明在1~m-1的区间内没有能够整除它的数，所以这个数一定是一个质数
- 只需遍历1~√n，大于√n的数如果没有遍历到一定是质数，且也不需要将后续的倍数标记，因为√n*√n >= n

class Solution_204_01 {
 public:
  int countPrimes(int n) {
    int cnt = 0;
    for (int i = 2; i < n; ++i) {
      if (isPrime(i)) ++cnt;
    }
    return cnt;
  }
  bool isPrime(int m) {
    for (int i = 2; i <= sqrt(m); ++i) {
      if (m % i == 0) return false;
    } 
    return true;
  }
};

class Solution_204_02 {
 public:
  int countPrimes(int n) {
    bool pArray[n + 1] = {0};
    int cnt = 0;
    for (int i = 2; i < n; ++i) {
      if (!pArray[i] && isPrime(i)) {
        ++cnt;
        for (int j = i; j < n; j += i) pArray[j] = true;
      }
    }
    return cnt;
  }
  bool isPrime(int m) {
    for (int i = 2; i <= sqrt(m); ++i) {
      if (m % i == 0) return false;
    }
    return true;
  }
};

class Solution_204_03 {
 public:
  int countPrimes(int n) {
    bool notPrime[n+1] = {0};
    int cnt = 0, limit = sqrt(n);
    for (int i = 2; i <= limit; ++i) {
      if (!notPrime[i]) {
        for (int j = i * i; j < n; j += i) {
          notPrime[j] = true;
        }
      }
    }
    for (int i = 2; i < n; ++i) {
      if (!notPrime[i]) ++cnt;
    }
    return cnt;
  }
};