<正文>
素数 (Prime) 及判定
定义
素数又称质数, 一个大于 1 的自然数, 除了 1 和它自身外, 不能整除其他自然数的数叫做质数, 否则称为合数.
1 既不是素数也不是合数.
判定
如何判定一个数是否是素数呢? 显然, 我们可以枚举这个数的因数, 如果存在除了它本身和 1 以外的因数, 那么这个数就是素数.
在枚举时, 有一个很简单的优化: 一个合数 \(n\)必有一个小于等于 \(\sqrt{n}\)的因数.
证明如下:
假设一个合数 \(n\)没有小于等于 \(\sqrt{n}\)的因数.
由于 \(n\)为合数, 所以除了 \(n\)与 \(1\)以外, 它至少还有两个因数 \(p_1(p_1>\sqrt{n})\)和 \(p_2(p_2>\sqrt{n})\), 满足 \(p_1p_2=n\).
与 \(p_1>\sqrt{n},p_2>\sqrt{n}\)矛盾, 故假设不成立.
所以我们得到了 \(O(\sqrt n)\)效率的素数判定算法.
- \(Code:\)
- inline bool check(k)
- {
- for(int i=2;i*i<=k;i++)
- if(k%i==0)return 0;
- return 1;
- }
筛法 (Sieve) 求素数
现在有一个新的问题模型, 如果我们需要求解 \(1-n\)的所有素数, 那么直接用判定法效率显然太低了. 我们需要更高效率的算法, 由此我们引入筛法.
埃氏筛法(The sieve of Eratosthenes)
这是筛法思想的基本模型. 根据算数基本定理, 我们得知:
\[k=p_1^{a_1}.p_2^{a_2}.....p_k^{a_k}\]
即任意一个数 \(k\)都是由若干素数相乘得到的.
那么我们可以枚举 \(2-n\)的每一个数, 如果这个数没被标记, 则说明这个数是素数, 记录这个数, 并标记这个数的所有倍数不是素数.
那么这样就可以求解 \(1-n\)的所有素数了. 时间复杂度为 \(O(n\ ln(ln\ n))\).
实现
这就是 OI 竞赛中最常用的素数求解算法了, 实现也非常简单.
- \(Code:\)
- #include<bits/stdc++.h>
- using namespace std;
- int cnt=0,n,flag[100080]={},Prime[100080]={};
- inline void sieve(void)
- {
- for(int i=2;i<=n;i++)
- {
- if(!flag[i])Prime[++cnt]=i;else continue;
- for(int j=i*2;j<=n;j+=i)flag[j]=true;
- }
- }
- int main(void)
- {
- cin>>n;
- sieve();
- for(int i=1;i<=cnt;i++)cout<<Prime[i]<<" ";
- cout<<endl;
- }
欧拉筛法(The sieve of Euler)
欧拉筛法就是基于埃氏筛法的优化.
在模拟埃氏筛法的过程中, 我们不难发现有很多合数会被它的各个素因子筛好几次, 我们可以基于这种情况进行优化: 每个合数必有一个最小素因子, 用这个因子筛掉合数
所以, 我们直接利用之前求出的素数进行筛数, 如果发现当前这个数已经是之前某个素数的倍数时, 那就说明这个数在以后会由某个更大的数乘以这个小素数筛去, 同理, 之后的筛数也是没有必要的, 这时候就可以跳出循环了.
这样, 我们就能保证每一个数只被筛一次, 就实现了线性时间复杂度的筛法.
实现
欧拉筛法和埃氏筛法大体相似, 但细节有所不同, 注意不要搞混.
- \(Code:\)
- #include<bits/stdc++.h>
- using namespace std;
- int cnt=0,n,flag[100080]={},Prime[100080]={};
- inline void seive(void)
- {
- for(int i=2;i<=n;i++)
- {
- if(!flag[i])Prime[++cnt]=i;
- // 注意, 这里没了 continue, 因为在筛某个数时需要用到它的最大因数, 而这个数可能是个合数, 所以不管是素数还是合数, 都要执行以下的筛数过程
- for(int j=1;j<=cnt&&i*Prime[j]<=n;j++)
- {
- flag[i*Prime[j]]=1;
- if(i%Prime[j]==0)break;
- }
- }
- }
- int main(void)
- {
- cin>>n;
- seive();
- for(int i=1;i<=cnt;i++)cout<<Prime[i]<<" ";
- cout<<endl;
- }
来源: https://www.cnblogs.com/Parsnip/p/10118093.html