筛法——求n以内质数个数_求n里面有多少个质数

预备知识：

1. 若一个数可以进行因数分解，则得到的两个数一定是有一个≤$\sqrt{x}$，另一个≥$\sqrt{x}$
2. 任何一个数都可以拆分为若干个质因数的乘积，如6=2*3，7=1*7 。

• 朴素筛

复杂度O(n$\sqrt{n}$)

#include<iostream>
using namespace std;
int plainSieve(int n)
{
   
    int p=0;
    if(n==2)
        return 1;
    if(n<2)
        return 0;
    p++;
    // i+=2优化步长
    for(int i=3;i<=n;i+=2)
    {
   
        int j;
        // j*j优化范围
        for(j=2;j*j<=i;j++)
            if(i%j==0)
                break;
        if(j*j>i)
            p++;
    }
    return p;
}
int main()
{
   
    int n;
    while(cin>>n)
        cout<<plainSieve(n)<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

• 埃氏筛

复杂度 O(nlglgn)

解释：当prime[i]为0时，说明 i 没有被筛到过，即 i 为质数。质数总数 p++
之后要将 i 的n以内的倍数 j 全部置为合数，prime[j]标记为1。
此后若筛到 j ，prime为1，j 为合数，直接跳过，进行下个数的判断

#define Max 1000010
int prime[Max]={
   0};
int EraSieve(int n)
{
   
    if(n<2)
        return 0;
    if(n==2)
        return 1;
    int p=0;
    prime[0]=prime[1]=1;
    for(int i=2;i<=n;i++)
    {
   
        if(prime[i]==0)
        {
   
            p++<
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18