LeetCode 204 Count Primes

Tag: 数学类题目 LeetCode Posted on 2022-03-01 10:40:15 Edited on 2022-03-01 10:57:51 Views: 123

概述

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)

未经允许,禁止转载,本文源站链接:https://iamazing.cn/