线性筛和埃氏筛

线性筛：

#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;
}

相关阅读:
CyberController手机外挂番外篇：源代码的二次修改
用Go实现网络流量解析和行为检测引擎
.NET 6 轻量级 WebApi 框架 FastEndpoints 入门
指针成员操作符
windows通过gitstats-master+gnuplot统计代码量
PowerShell 命令窗口执行 pnpm 命令报错无法加载文件 pnpm.ps1，因为在此系统上禁止运行脚本
在10.24这个特殊的日子里，带你详细解读1024！
《ASP.NET Core 6框架揭秘》样章发布[200页/5章]
嵌入式分享合集93
【Docker安装部署Zookeeper+Kafka集群详细教程、部署过程中遇到问题&解决方案、测试集群是否部署成功】

原文地址：https://blog.csdn.net/yusen_123/article/details/133500780