题解 | #返回小于 N 的质数个数# 质数筛选的三种优化

一、原式版本

bool is_prime(int n)
{
    for(int i = 2; i < n; i++)
    {
        if(n % i == 0)
            return false;
    }
    return true;
}

int main()
{
    int n = 0, ans = 0;
    scanf("%d", &n);
    for(int i = 2; i < n; i++)
    {
        if(is_prime(i))
            ans++;
    }
    printf("%d", ans);
    return 0;
}

二、境界一：对于枚举法的优化

①优化1

for(int i = 3; i < n; i+= 2)
{
    if(is_prime(i))
        ans++;
}

显而易见，偶数不可能是质数，所以在枚举的时候，可以一次“走两步”

②优化②

bool is_prime(int n)
{
    for(int i = 2; i * i <= n; i++)  // 别忘了等于号了
    {
        if(n % i == 0)
            return false;
    }
    return true;
}

​ 如果A不为质数，那么必然存在A=B*C（2<=B<C<A）。所以只要说明B的存在就可以说明A必然是合数。而B最大值 为根号A，所以只要枚举到 i * i<=A即可判断是否为质数。

三、境界二：埃氏筛法

#include <stdio.h>
#include <stdlib.h>
typedef long long ll;

int main()
{
    int n = 0, ans = 0;
    scanf("%d", &n);
    bool* f = (bool *)calloc(n + 1, sizeof(bool));
    f[1] = 1;

    for(int i = 2; i < n; i++)
    {
        if(!f[i])
        {
            ans++;
            for(ll j = (ll)i * i; j < n; j+= i)
            {
                f[j] = 1;
            }
        }
    }
    printf("%d", ans);
}

 在这里只是呈现各种优化思路，详细讲解请参考相关博文 素数筛选——枚举法+埃氏筛法+欧拉筛法（C语言实现）

四、境界三：欧拉筛法

int main()
{
    int n = 0;
    scanf("%d", &n);
    bool* flag = (bool*)calloc(n, sizeof(bool));
    int cnt = 0;
    int prime[n+1];

    for (int i = 2; i < n; i++)
    {
        if (!flag[i])
        {
            prime[++cnt] = i;//prime数组记录素数
        }
        for (int j = 1; i * prime[j] < n; j++)//筛去合数
        {
            flag[i * prime[j]] = 1;
            if (i % prime[j] == 0)//精髓
                break;
        }
    }
    printf("%d", cnt);
}

 在这里只是呈现各种优化思路，详细讲解请参考相关博文 素数筛选——枚举法+埃氏筛法+欧拉筛法（C语言实现）