204. Count Primes.md

题目

204. Count Primes

思路

刚开始是想遍历到n， 逐个判断计数。复杂度是O(n^2)，17/20超时

后来使用厄拉多塞筛法,大概就是删除n范围内每个质数的倍数,剩下的就都是质数了。 92ms 70.38%

一篇题解

代码

class Solution {
public:
    bool isprime(int n){
        if(n==0||n==1) return false;
        for(int i=2;i<n;i++)
            if(n%i==0)return false;
        return true;
    }
    
    int countPrimes(int n) {
        int num=0;
        for(int i=0;i<n;i++){
            if(isprime(i)) num++;
        }
        return num;
    }
};