当前位置: 首页 > news >正文

质数筛

重新理解线性筛, 推荐文章

中心思想, 每个合数都被他的最小质因数筛去。

合数 \(u = i \times p\)\(p\) 是它的最小质因数,\(u\) 是被 \(i \times p\) 筛去的,\(i\) 一定小于 \(u\),那么在算法运行到 \(u\) 之前,\(u\) 一定会被标记。

if ((i % priems[j]) == 0) break; 为什么 break
如果 i 可以被质数%成 \(0\) 那么 i = priems[j] * x; 那么对于下一个数 i * primes[j + 1] 就等价 primes[j] * x * primes[j + 1] 因为是从小到大存的质数,那么 primes[j] < primes[j + 1] 因为是用最小质因子去筛,用 primes[j + 1] 就不如 primes[j] 小(实际上这里 \(p_j\)\(i\) 的最小质因子,因为从小到大排的质数,\(p_j\) 是第一个可以消掉 \(i\) 的质数, 肯定是最小质因数)所以跳过防止重复筛,并且后面的也不要了,因为我们知道可以用primes[j]能消掉。

在筛数时 \(p <= i\)
证明:因为 \(p\) 是由 \(i\) 筛出来的,所以理论上 \(p \leq i\)

为何在标记合数时,for (int j = 1; primes[j] <= n / i; j ++ ) 不用判断 j <= cnt:在当前已经求出了 \([1, i]\) 的质数,包含 \(i\) 的所有质因子,那么 \(i\) 总会被它含有的质因子成功取模为 \(0\),而 break 跳出循环,也就不会枚举到 \(cnt\) 之后。

线性筛 (欧拉筛) \(O(n)\)

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 1000010;int primes[N];
int n, cnt;
bool st[N];int main()
{cin >> n;for (int i = 2; i <= n; i ++ ){if (!st[i]) primes[ ++ cnt] = i; // 加入质数// primes[j] <= n / i是为了防止筛的数超过nfor (int j = 1; primes[j] <= n / i; j ++ ){st[primes[j] * i] = true; // 肯定是合数if (i % primes[j] == 0) break;}}cout << cnt << endl;return 0;
}

最后提醒一点,关于 \(n\),如果你上面循环写的是 i < n 就相当于,\(n\) 变成了 \(n - 1\),那么下面的循环就应该写 prime[j] <= (n - 1) / i 而不是 prime[j] < n / i,这是一个容易搞错的地方,一定要知道我们的界限。

如果写成了 prime[j] < n / i,就相当于写成了 prime <= (n / i - 1) 就相当于 prime[j] * i <= n - i,就相当于缩小了 \(n - 1\),就会使得部分应该标记的合数,没被标记,这就导致这些合数变成了质数,就导致了我们质数筛的错误。这种错误不易发现,因此一定要注意 \(n\) 的含义,使用标准、稳定的写法。

埃氏筛 \(\operatorname O(n\log \log n)\)

算法的原理为:用每个质数,把它的倍数给筛去,而一个数可能由多个不同质数组成,所以会重复标记。

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 1000010;int primes[N];
int n, cnt;
bool st[N];int main()
{cin >> n;for (int i = 2; i <= n; i ++ ){if (!st[i]) primes[ ++ cnt] = i;else continue;for (int j = 2; j <= n / i; j ++ )st[j * i] = true;}cout << cnt << endl;return 0;
}

下面是老码风代码

线性筛 (欧拉筛) O(n)

#include<iostream>
using namespace std;
const int N=1e6+10;
int  priems[N],cnt=0;
bool st[N];bool get_priems(int n)
{for (int i=2;i<=n;i++){if (!st[i]) priems[cnt++]=i;for (int j=0;priems[j]<=n/i;j++){st[priems[j]*i]=true;if ((i % priems[j]) == 0) break;}}
}
int main()
{int n;cin>>n;get_priems(n);cout<<cnt;return 0;
}

埃氏筛 O(nloglogn)约等于O(n)

#include<iostream>
using namespace std;const int N=1001001;
int priems[N],cnt;
bool st[N];
int get_priems(int n)
{for (int i=2;i <= n;i++){if (!st[i]) {priems[cnt++]=i;for (int j=i+i; j<=n;j+=i) st[j]=true;}}
}int main()
{int n;cin>>n;get_priems(n);cout<<cnt;return 0;}
```重新理解线性筛, 推荐[文章](https://zhuanlan.zhihu.com/p/100051075) 中心思想, 每个**合数**都被他的**最小质因数**筛去。合数 $u = i \times p$,$p$ 是它的最小质因数,$u$ 是被 $i \times p$ 筛去的,$i$ 一定小于 $u$,那么在算法运行到 $u$ 之前,$u$ 一定会被标记。`if ((i % priems[j]) == 0) break;` 为什么 break
如果 `i` 可以被质数%成 $0$ 那么 `i = priems[j] * x;` 那么对于下一个数 `i * primes[j + 1]` 就等价 `primes[j] * x * primes[j + 1]` 因为是从小到大存的质数,那么 `primes[j] < primes[j + 1]` 因为是用最小质因子去筛,用 `primes[j + 1]` 就不如 `primes[j]` 小(实际上这里 $p_j$ 是 $i$ 的最小质因子,因为从小到大排的质数,$p_j$ 是第一个可以消掉 $i$ 的质数, 肯定是最小质因数)所以跳过防止重复筛,并且后面的也不要了,因为我们知道可以用`primes[j]`能消掉。在筛数时 $p <= i$ 
证明:因为 $p$ 是由 $i$ 筛出来的,所以理论上 $p \leq i$。为何在标记合数时,`for (int j = 1; primes[j] <= n / i; j ++ )` 不用判断 `j <= cnt`:在当前已经求出了 $[1, i]$ 的质数,包含 $i$ 的所有质因子,那么 $i$ 总会被它含有的质因子成功取模为 $0$,而 `break` 跳出循环,也就不会枚举到 $cnt$ 之后。 #### 线性筛 (欧拉筛) $O(n)$```cpp
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 1000010;int primes[N];
int n, cnt;
bool st[N];int main()
{cin >> n;for (int i = 2; i <= n; i ++ ){if (!st[i]) primes[ ++ cnt] = i; // 加入质数// primes[j] <= n / i是为了防止筛的数超过nfor (int j = 1; primes[j] <= n / i; j ++ ){st[primes[j] * i] = true; // 肯定是合数if (i % primes[j] == 0) break;}}cout << cnt << endl;return 0;
}

最后提醒一点,关于 \(n\),如果你上面循环写的是 i < n 就相当于,\(n\) 变成了 \(n - 1\),那么下面的循环就应该写 prime[j] <= (n - 1) / i 而不是 prime[j] < n / i,这是一个容易搞错的地方,一定要知道我们的界限。

如果写成了 prime[j] < n / i,就相当于写成了 prime <= (n / i - 1) 就相当于 prime[j] * i <= n - i,就相当于缩小了 \(n - 1\),就会使得部分应该标记的合数,没被标记,这就导致这些合数变成了质数,就导致了我们质数筛的错误。这种错误不易发现,因此一定要注意 \(n\) 的含义,使用标准、稳定的写法。

埃氏筛 \(\operatorname O(n\log \log n)\)

算法的原理为:用每个质数,把它的倍数给筛去,而一个数可能由多个不同质数组成,所以会重复标记。

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 1000010;int primes[N];
int n, cnt;
bool st[N];int main()
{cin >> n;for (int i = 2; i <= n; i ++ ){if (!st[i]) primes[ ++ cnt] = i;else continue;for (int j = 2; j <= n / i; j ++ )st[j * i] = true;}cout << cnt << endl;return 0;
}

下面是老码风代码

线性筛 (欧拉筛) O(n)

#include<iostream>
using namespace std;
const int N=1e6+10;
int  priems[N],cnt=0;
bool st[N];bool get_priems(int n)
{for (int i=2;i<=n;i++){if (!st[i]) priems[cnt++]=i;for (int j=0;priems[j]<=n/i;j++){st[priems[j]*i]=true;if ((i % priems[j]) == 0) break;}}
}
int main()
{int n;cin>>n;get_priems(n);cout<<cnt;return 0;
}

埃氏筛 O(nloglogn)约等于O(n)

#include<iostream>
using namespace std;const int N=1001001;
int priems[N],cnt;
bool st[N];
int get_priems(int n)
{for (int i=2;i <= n;i++){if (!st[i]) {priems[cnt++]=i;for (int j=i+i; j<=n;j+=i) st[j]=true;}}
}int main()
{int n;cin>>n;get_priems(n);cout<<cnt;return 0;}
```重新理解线性筛, 推荐[文章](https://zhuanlan.zhihu.com/p/100051075) 中心思想, 每个**合数**都被他的**最小质因数**筛去。合数 $u = i \times p$,$p$ 是它的最小质因数,$u$ 是被 $i \times p$ 筛去的,$i$ 一定小于 $u$,那么在算法运行到 $u$ 之前,$u$ 一定会被标记。`if ((i % priems[j]) == 0) break;` 为什么 break
如果 `i` 可以被质数%成 $0$ 那么 `i = priems[j] * x;` 那么对于下一个数 `i * primes[j + 1]` 就等价 `primes[j] * x * primes[j + 1]` 因为是从小到大存的质数,那么 `primes[j] < primes[j + 1]` 因为是用最小质因子去筛,用 `primes[j + 1]` 就不如 `primes[j]` 小(实际上这里 $p_j$ 是 $i$ 的最小质因子,因为从小到大排的质数,$p_j$ 是第一个可以消掉 $i$ 的质数, 肯定是最小质因数)所以跳过防止重复筛,并且后面的也不要了,因为我们知道可以用`primes[j]`能消掉。在筛数时 $p <= i$ 
证明:因为 $p$ 是由 $i$ 筛出来的,所以理论上 $p \leq i$。为何在标记合数时,`for (int j = 1; primes[j] <= n / i; j ++ )` 不用判断 `j <= cnt`:在当前已经求出了 $[1, i]$ 的质数,包含 $i$ 的所有质因子,那么 $i$ 总会被它含有的质因子成功取模为 $0$,而 `break` 跳出循环,也就不会枚举到 $cnt$ 之后。 #### 线性筛 (欧拉筛) $O(n)$```cpp
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 1000010;int primes[N];
int n, cnt;
bool st[N];int main()
{cin >> n;for (int i = 2; i <= n; i ++ ){if (!st[i]) primes[ ++ cnt] = i; // 加入质数// primes[j] <= n / i是为了防止筛的数超过nfor (int j = 1; primes[j] <= n / i; j ++ ){st[primes[j] * i] = true; // 肯定是合数if (i % primes[j] == 0) break;}}cout << cnt << endl;return 0;
}

最后提醒一点,关于 \(n\),如果你上面循环写的是 i < n 就相当于,\(n\) 变成了 \(n - 1\),那么下面的循环就应该写 prime[j] <= (n - 1) / i 而不是 prime[j] < n / i,这是一个容易搞错的地方,一定要知道我们的界限。

如果写成了 prime[j] < n / i,就相当于写成了 prime <= (n / i - 1) 就相当于 prime[j] * i <= n - i,就相当于缩小了 \(n - 1\),就会使得部分应该标记的合数,没被标记,这就导致这些合数变成了质数,就导致了我们质数筛的错误。这种错误不易发现,因此一定要注意 \(n\) 的含义,使用标准、稳定的写法。

埃氏筛 \(\operatorname O(n\log \log n)\)

算法的原理为:用每个质数,把它的倍数给筛去,而一个数可能由多个不同质数组成,所以会重复标记。

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 1000010;int primes[N];
int n, cnt;
bool st[N];int main()
{cin >> n;for (int i = 2; i <= n; i ++ ){if (!st[i]) primes[ ++ cnt] = i;else continue;for (int j = 2; j <= n / i; j ++ )st[j * i] = true;}cout << cnt << endl;return 0;
}

下面是老码风代码

线性筛 (欧拉筛) O(n)

#include<iostream>
using namespace std;
const int N=1e6+10;
int  priems[N],cnt=0;
bool st[N];bool get_priems(int n)
{for (int i=2;i<=n;i++){if (!st[i]) priems[cnt++]=i;for (int j=0;priems[j]<=n/i;j++){st[priems[j]*i]=true;if ((i % priems[j]) == 0) break;}}
}
int main()
{int n;cin>>n;get_priems(n);cout<<cnt;return 0;
}

埃氏筛 O(nloglogn)约等于O(n)

#include<iostream>
using namespace std;const int N=1001001;
int priems[N],cnt;
bool st[N];
int get_priems(int n)
{for (int i=2;i <= n;i++){if (!st[i]) {priems[cnt++]=i;for (int j=i+i; j<=n;j+=i) st[j]=true;}}
}int main()
{int n;cin>>n;get_priems(n);cout<<cnt;return 0;}
http://www.hskmm.com/?act=detail&tid=20294

相关文章:

  • pnpm 安装后无法使用
  • 数学解题中常见的“漏解”情况分析
  • 图册
  • 简单的Powershell脚本
  • 基于YOLO8+flask+layui的行人跌倒行为检测系统【源码+模型+数据集】 - 详解
  • 环形链表-leetcode
  • [ABC425C] Rotate and Sum Query 题解
  • 线程--基本使用、线程常用方法
  • 酵母表面展示技术:从蛋白分析到多领域应用,解锁可持续发展的生物新工具
  • 9/28数学错题分析
  • linux查找指定字符串的三种方法 - 指南
  • task
  • SQL逐字稿
  • 实用指南:嵌入式面试高频(十二)!!!C++语言(嵌入式八股文,嵌入式面经)c++11新特性
  • 2025 年粒度仪厂家推荐山东耐克特分析仪器,粒度分析仪,喷雾,激光,纳米,在线,图像粒形,干湿两用粒度仪公司推荐
  • 2025年匹克球厂家推荐义乌亿宁体育 ,滚塑匹克球,匹克球网,静音匹克球,LED 发光匹克球,专业比赛匹克球公司推荐
  • 2025 年粒度仪厂家推荐山东耐克特分析仪器,电位仪 / 纳米粒度及 Zeta 电位仪 / Zeta 电位仪公司推荐
  • 2025攻丝机厂家 TOP 企业品牌推荐排行榜,全自动,半自动,转盘,伺服,平推,全自动钻孔,半自动钻孔攻丝机公司推荐
  • 实用指南:微信公众号网页调试, 某讯参数,drviceToken V2
  • 2025 年芝麻灰厂家 TOP 企业品牌推荐排行榜,芝麻灰路沿石,花岗岩石材,火烧板,地铺石,板材,挡车球,桥栏杆,楼梯踏步,门牌石,水篦子公司推荐
  • 2025.9.28
  • 深入解析:宝塔面板搭建RustDesk教程:告别命令行,一键拥有私有远程桌面
  • Windows 安装达梦数据库
  • 有旋Treap
  • xxO
  • 情绪识别论文阅读——Eyemotion - 详解
  • 2025年山东设备回收公司TOP交易服务推荐排行榜,济宁,梁山设备回收,二手,饮料,食品,制药,实验室,生产线,化工厂,废旧,大型,专业设备回收公司推荐
  • 做了个TIFF图片格式转换工具,感觉怎么样?
  • C#后遗症,掉了个坑,特此记录
  • 曾记否 -- Words to be remembered 2025.9.28