【Leetcode刷题笔记】204. Count Primes 快速求N以内的素数个数

int countPrimes(int n) {
    if(n<=2)return 0;
    int ans = 1;
    vector<bool>res(n,false);
    int upper = sqrt(n);
    for(int i=3;i<n;i=i+2){
        if(!res[i]){
        ans++;
        if(i>upper)continue;
        for(int j=i*i;j<n;j=j+i*2){
            res[j]=true;
        }
        }
    }
    return ans; }

原理：
筛素数的基本方法是用来筛选出一定范围内的素数素数筛法的基本原理，利用的是素数p只有1和p

这两个约数，并且一个数的约数一定不大于本身，素数筛法的过程：

把从1开始的、某一范围内的正整数从小到大顺序排列，

1不是素数，首先把它筛掉。

剩下的数中选择最小的数是素数，然后去掉它的倍数。

依次类推，直到筛子为空时结束。

求解用途：

素数筛法经常作为一道题的一部分用来打一定范围内素数表，