0_素数筛

LeetCode 204： Count Primes

• 方法一：枚举
  
  • 枚举每个数判断其是否是质数
    
    • 质数的定义：在大于 11 的自然数中，除了 11 和它本身以外不再有其他因数的自然数
      
    • 因此对于每个数 x，我们可以从小到大枚举 [2,x-1 中的每个数 y，判断 y是否为 x 的因数。但这样判断一个数是否为质数的时间复杂度最差情况下会到 O(n），无法通过所有测试数据。
      
    • 若y为x的因数，则x/y也为x的因数，较小数一定落在[2,sqrt(x)]之间，因此单次检查区间为[2,sqrt(x)]，单次时间复杂度降低到O(n*sqrt(n))
      
  • 时间复杂度 O(n*sqrt(n)) 空间复杂度：O(1)
    
  • 参考代码：
    
  • private:
  • bool isPrime(int num) {
  • if (num <= 1) return false;
  • if (num == 2 || num == 3) return true;
  • int bound = int(sqrt(num));
  • for (int i = 2; i <= bound; i++)
  • if (num % i == 0)
  • return false;
  • return true;
  • }
  • public:
  • int countPrimes(int n) {
  • if (n <= 1) return 0;
  • int count = 0;
  • for(int num = 2; num <= n - 1; num++)
  • if (isPrime(num)) count += 1;
  • return count;
  • }
• 方法二：埃氏筛
  
  • 枚举法没有考虑到数之间的相关性。该算法由Eratosthenes提出，称为厄拉多塞筛法
    
  • 考虑这样一个事实，若x为质数，则x的倍数2x、3x必不为质数，我们可以从这里入手。
    
  • 设isPrime[i]表示数字i是否是质数，若是则为1，否则为0。从小到大遍历每个数
    
    • 若这个数为质数，则除该质数本身外，将其所有的倍数都标记为合数，即为0
      
    • 另一方面，当从小到达遍历到达数x时，若为合数，则它一定是 某个 小于x的质数 y 的 整数倍，因此在我们遍历到y时，一定会标记isPrime(x)=0
      
      • 进一步优化，对于一个质数x，应当直接从x*x处开始标记，因为这些数一定在 x 之前 被 其他质数的倍数标记，如2的倍数2x，3的倍数3x
        
  • 时间复杂度：O(n*logn) 空间复杂度：O(n)
    
  • 参考代码：
    
• int countPrimes_Eratosthenes(int n) {
• vector isPrime(n, true);
• int res = 0;
• for (int num = 2; num < n; ++num) {
• if (isPrime[num]) {
• res += 1;
• if ((long long)num * num < n)
• for (int j = num * num; j < n; j += num)
• isPrime[j] = false;
• }
• }
• return res;
• }
• 方法三：线性筛
  
  • Eratosthenes筛仍然存在冗余操作，它会同时被3、5两个数标记为合数，因此我们优化目标为让每个合数只被标记一次
    
  • 相比于埃氏筛
    
    • 多维护一个primes数组表示当前得到的质数集合。从小到大遍历，若当前的数x为质数，则将其加入primes数组
      
    • [标记过程]不再当且仅当x为质数时才进行，而是对于每个整数x都进行。
      
      • 对于整数 x ，我们不再标记其所有的倍数 xx，x(x+1)，而只标记 质数集合中的数 与 x 相乘 得到的数，即 xprimes_0，xprimes_1，…，直到x mod primes_i = 0时，结束标记。
        
      • 核心：若x可以被primes_i整除，则对于合数 y = xprimes_i+1而言，它一定在后面遍历到（x/primes_i） primes_i+1时，被标记，即保证了每个合数只会被其最小的质因数筛去，每个合数只会被标记一次。
        
  • 时间复杂度 O(n) 空间复杂度: O(n)
    
  • 参考代码：
    
• int countPrimes_linear(int n) {
• vector primes;
• vector isPrime(n, true);
• for (int num = 2; num < n; ++num) {
• if (isPrime[num])
• primes.push_back(num);
• for (int i = 0;i < primes.size() && num * primes[i] < n; ++i) {
• isPrime[num * primes[i]] = false;
• if (num % primes[i] == 0)
• break;
• }
• }
• return primes.size();
• }