• 线性筛和埃氏筛

    线性筛：

    #define _CRT_SECURE_NO_WARNINGS 
    #include
    #include
    #include
    #include
    #include
    #include
    #include<ctime>
    #include
    #include
    #include<stack>
    #include
    #include
    #include
    #include
    #include
    #include
    using namespace std;
    #define LL  long long
    const int N = 1e6+1000;
    const long long  mod = 1e9 + 7;
    #define  rep(i,a,b) for (int i = a; i <= b; i++) 
    #define per(i, a, b) for(int  i=a;i>=b;i--)
    int n,cnt;
    int a[N],x,su[N];
    unordered_map p;
    void into()
    {
        a[0] = a[1] = 1;
        for (int i = 2; i <= n; i++)
        {
            if (!a[i])
                su[++cnt] = i;
            for (int j = 1; su[j] <= n / i; j++)
            {
                a[su[j] * i] = 1;
                if (i % su[j] == 0) break;
            }
            
        }
    }
    int main()
    {   
        cin >>n;
        into();
        cout << cnt << endl;
        return 0;
    }

    埃氏筛：

    #define _CRT_SECURE_NO_WARNINGS 
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    using namespace std;
    #define LL  long long
    const int N = 1e5 + 1000;
    const long long  mod = 1e9 + 7;
    #define  rep(i,a,b) for (int i = a; i <= b; i++) 
    #define per(i, a, b) for(int  i=a;i>=b;i--)
    int n, cnt;
    int su[N], a[N], x, flag = 0;
    unordered_map p;
    void into()
    {
        a[0] = a[1] = 1;
        rep(i, 1, N)
        {
            if (a[i]) continue;
            su[++cnt] = i;
            p[i] = 1;
            for (int j = 2 * i; j <= N; j += i)
                a[j] = 1;
        }
    }
    int main()
    {
        into();
        return 0;
    }

  • 相关阅读:
    半球体容器漏水体积微分问题
    Vue组件库必备 Sass(Dart) 知识
    【store商城项目02】登录功能的开发
    代码随想录-day3
    学习c#的第十九天
    图神经网络（GNN）综述的总结
    Golang | Leetcode Golang题解之第50题Pow(x,n)
    Springboot01入门
    AI：10-基于TensorFlow的玉米病害识别
    8.2模拟赛总结
  • 原文地址：https://blog.csdn.net/yusen_123/article/details/133500780