LeetCode 204 Count Primes

    
        标签：
        
            数学类题目
        
            LeetCode
        
    发布于：2022-03-01 10:40:15
    编辑于：2022-03-01 10:57:51
    浏览量：706

概述

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

暴力法

遍历到 n，并判断其是否为质数，判断方式是用已有的质数对其求余，看余数是否为 0，如果为 0 则非质数。

class Solution {
public:
    vector<int> primes;
    int countPrimes(int n) {
        for (int i = 2; i < n; i ++) {
            if (isPrime(i)) primes.push_back(i);
        }
        return primes.size();
    }
    
    bool isPrime(int n) {
        for (auto p : primes) {
            if (n % p == 0) return false;
        }
        return true;
    }
};

时间复杂度 O(n^2)，TLE 了。

暴力法 + 因子对称优化

如果质数已经大于 sqrt(n) 了，则后面不可能有能整除其的质数了，因为这样的话就需要一个小于 sqrt(n) 的可以整除其的质数，而我们已经检查过这一点不成立了。

时间复杂度优化到 O(n^1.5)，TLE 了。

class Solution {
public:
    vector<int> primes;
    int countPrimes(int n) {
        for (int i = 2; i < n; i ++) {
            if (isPrime(i)) primes.push_back(i);
        }
        return primes.size();
    }
    
    bool isPrime(int n) {
        int stop = sqrt(n);
        for (auto p : primes) {
            if (p > stop) break;
            if (n % p == 0) return false;
        }
        return true;
    }
};

筛选法求质数

https://labuladong.gitee.io/algo/4/30/119/

class Solution {
public:
    int countPrimes(int n) {
        if (n <= 2) return 0;
        vector<bool> isPrime(n, true);
        isPrime[0] = false;
        isPrime[1] = false;
        int stop = sqrt(n);
        for (int i = 1; i <= stop; i ++) {
            if (isPrime[i]) {
                for (int j = 2 * i; j < n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        int count = 0;
        for (int i = 0; i < n; i ++) {
            if (isPrime[i]) count ++;
        }
        return count;
    }
};

内层的时间复杂度不好求啊。。。

内层的 for 循环依然存在计算冗余，从 2 * i 开始的话其可能已经被标记过了。

观察计算序列：2 * i, 3 * i, 4 * i, ..., i * i, ..., n-1 * i，我们发现 i * i 之前的起始已经被算过了，所以内层 for 循环可以优化为：

for (int j = i * i; j < n; j += i)

Links: leetcode-204-count-primes