Leetcode:204. 计数质数

今天的每日题目就有点小水啦。

题目链接: 204. 计数质数

题目:

侃侃:

这道题好像没有什么要说的,因为 n 的范围是 5e6 ,所以在判断一个数是不是素数的时候要进行降维处理,除了下面我采用的方式,大家也可以采用 埃式筛法,时间复杂度会大大的降低。

Code:

class Solution {
public:
    // 判断一个数是不是素数
    int isPrime(int n) {
        for(int i = 2; i * i <= n; i ++) {
            if(n % i == 0) return 0;
        }
        return 1;
    }

    int countPrimes(int n) {
        int ans = 0;
        // 读清题意,是 < n
        for(int i = 2; i < n; i ++) {
            if(isPrime(i)) ans ++;
        }
        return ans;
    }
};