线性筛和埃氏筛

线性筛：

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

相关阅读:
tab切换（用jQuery实现）?
数学基础之概率论1
【毕业设计】基于stm32的智能扫地机器人设计与实现 - 单片机物联网
【力扣】单调栈：901. 股票价格跨度
计算机网络——物理层（传输方式）
修改容器的hosts配置
【Linux 进程通信】消息队列
C++游戏设计教程（3）—— 字体的颜色
使用正确的命令重启WSL子系统
UltraISO做u盘镜像启动盘

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