计数质数-----枚举法和埃氏筛-526互联

给定整数 n ，返回 所有小于非负整数 n 的质数的数量

方法一：

利用枚举的方法，但是会超时

 1 class Solution {
 2 public:
 3     int countPrimes(int n) {
 4         int res=0;
 5         if(n==0||n==1){
 6             return 0;
 7         }
 8         for(int i=2;i<n;i++){
 9             bool judge=true;
10             for(int j=2;j*j<=i;j++){ ##注意此处只需让j的平方小于i即可，因为考虑到y是x的因数，那么y/x也必然是x的因数，那么我们只需要选择这两个因数当中较小的一
个即可，而该叫小的数的范围必然是在[2,√n],因此时间复杂度就从O(n)变成了O(logn)。
11                 if(i%j==0){
12                     judge = false;
13                     break;
14                 }
15             }
16             if(judge){
17                 res++;
18             }
19         }
20         return res;
21     }
22 };

方法二：

埃氏筛：

　　枚举没有考虑到数与数的关联性，因此难以再继续优化时间复杂度。接下来我们介绍一个常见的算法，该算法由希腊数学家厄拉多塞（Eratosthenes\rm EratosthenesEratosthenes）提出，称为厄拉多塞筛法，简称埃氏筛。

　　我们考虑这样一个事实：如果 xxx 是质数，那么大于 x的 x的倍数 2x,3x,…一定不是质数，因此我们可以从这里入手。

　　我们设 isPrime[i] 表示数 i 是不是质数，如果是质数则为 1，否则为 0。从小到大遍历每个数，如果这个数为质数，则将其所有的倍数都标记为合数（除了该质数本身），即 0，这样在运行结束的时候我们即能知道质数的个数。

　　这种方法的正确性是比较显然的：这种方法显然不会将质数标记成合数；另一方面，当从小到大遍历到数 x 时，倘若它是合数，则它一定是某个小于 x 的质数 y 的整数倍，故根据此方法的步骤，我们在遍历到 y时，就一定会在此时将 x 标记为 isPrime[x]=0。因此，这种方法也不会将合数标记为质数。

　　当然这里还可以继续优化，对于一个质数 x，如果按上文说的我们从 2x 开始标记其实是冗余的，应该直接从 x⋅x开始标记，因为 2x,3x,…这些数一定在 x 之前就被其他数的倍数标记过了，例如 2 的所有倍数，3 的所有倍数等

using namespace::std;
class Solution {
public:
    int countPrimes(int n){
        vector<int> isPrime(n, 1);
        int ans = 0;
        for(int i=2;i<n;i++){
            if(isPrime[i]){
                ans++;
                if((long long)i*i<n){
                    for(int j=i*i;j<n;j+=i){
                        isPrime[j]=0;
                    }
                }
            }
        }
        return ans;
    }
};

2023-08-18

02:45:22

质数回文palindromes usaco1