关于数论
数论是纯粹数学的分支，主要研究整数的性质，而数论又分为初等数论和高等数论，其中我们研究的方向是初等数论
规范
由于数论是研究整数数学，所以今后使用的未知数都有一个隐含条件$x \in N$
素数
聊到整数就免不了谈素数，数论种素数的定义大家小学的时候都学过，所谓素数，就是因子只有1和它本身的数，最小的素数是2。
素数判定
下面有这样一个问题，任意给定一个x,请判断这个数是不是素数。
分析
第一种方法很简单——通过定义来判断，即从2开始循环到x-1，如果里面有它的因子，那么它就不是，如果没有它就是，使用定义法判断素数的代码很好写，可以自己动手实践一下
查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include <iostream>
using namespace std;
bool judge(int x)
{
if(i==1)
retuirn false;
for (int i = 2; i < x; i++)
if (!(x%i))
return false;
return true;
}
int main()
{
int x;
cin>>x;
if (judge(x))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
|
素数判定的优化
考虑两个数a，b相乘等于x的情况。设$c=\sqrt x$,那么若$a \leq c$,则$b \geq c$,因此，x的因子一定是$[1,\sqrt x]$与$[\sqrt x+1,x]$一一对应的。于是我们就能做如下优化
查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include <iostream>
using namespace std;
bool judge(int x)
{
if(i==1)
return false;
for (int i = 2; i*i <= x; i++)
if (!(x%i))
return false;
return true;
}
int main()
{
int x;
cin>>x;
if (judge(x))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
|
查找$[1,N]$中的素数
学会了判断一个数是否为素数之后，我们就会思考如果有N个数，那么我们要如何查找这N个数中的所有素数呢，很容易想到的就是使用$O(N\sqrt N)$的算法，每个都判断一遍，是素数就记录，具体代码如下：
查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| #include <iostream>
#include <cstring>
using namespace std;
const int maxn=1e5+10;
int vis[maxn];
bool judge(int x)
{
if(x==1)
return false;
for (int i = 2; i*i <= x; i++)
if (!(x%i))
return false;
return true;
}
int main()
{
int n;
cin>>n;
memset(vis,false,sizeof(vis));
for (int i = 1; i <= n; i++)
if(judge(i))
vis[i]=true;
for (int i = 1; i <= n; i++)
if(vis[i])
cout<<i<<endl;
}
|
优化
如果是计算N个数中的素数个数使用之前的方法复杂度是$O(n\sqrt n)$，如果n取1e6，很显然会TLE，那么我们考虑更快的方法。如果一数是素数，那么它的倍数肯定是合数，于是当我们找到一个素数时，把他在N范围内的所有倍数到标记为和数就行了，那么读到这里大家肯定要问了，为什么只要把素数的倍数标为合数，就能把所有合数都标记上了呢，这里涉及到一个唯一分解定理（任何合数，都能被唯一的分解为有限个素数的乘积），在以后的学习中我们将会谈到它，而这个筛出素数的算法就叫埃拉托斯特尼筛法，或者叫埃氏筛法，简称埃筛，下面看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #include <iostream>
#include <cstring>
using namespace std;
const int maxn=1e5+10;
bool isprime[maxn];
void find(int n)
{
isprime[1]=false;
for (int i = 2; i <= n; i++)
isprime[i]=true;
for (int i = 2; i <= n; i++)
if (isprime[i])
for (size_t j = 2*i; j <= n; j+=i)
isprime[j]=false;
}
int main()
{
int n;
cin>>n;
find(n);
for (int i = 1; i <= n; i++) {
if(isprime[i])
cout<<i<<endl;
}
}
|
再优化
如果使用之前的算法，那么对于数字6来说，它既会被数字2搜到，也会被数字3搜到，这个算法的复杂度是$O(n\log (\log n))$,于是我们考虑能不能避免重复搜索，首先，由于之前谈到数的因子是成对存在的，所以在筛除的过程中，我们只需要使用$\sqrt n$之前的数去筛除即可，再者，对于一个数i，在考虑另一个数j与他相乘构成合数时，如果$ j < i $，那么我在之前使用j做筛除的时候已经把$j\times i$筛除掉了，所以我们每次只需要从$i\times i$开始筛就行了，代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #include <iostream>
#include <cstring>
using namespace std;
const int maxn=1e5+10;
bool isprime[maxn];
void find(int n)
{
isprime[1]=false;
for (int i = 2; i <= n; i++)
isprime[i]=true;
for (int i = 2; i*i <= n; i++)
if (isprime[i])
for (size_t j = i*i; j <= n; j+=i)
isprime[j]=false;
}
int main()
{
int n;
cin>>n;
find(n);
for (int i = 1; i <= n; i++) {
if(isprime[i])
cout<<i<<endl;
}
}
|
终极优化
当时间已经无法直接得到优化，那我们通常会去考虑使用适量的空间来间接的优化时间，算法中有很多这样用空间换时间的例子，线性筛法，也就是欧拉筛法，就是其中之一。以埃筛为基础思想，埃筛中是使用一个素数为基础，去乘以其他数，来筛除合数，那我们考虑能否以任意的一个数为基础，去乘以所有已经确认的素数，来筛除合数？
对于我们所选择的数，它包含两种情况：
Ⅰ.这个数是素数
Ⅱ.这个数是合数
对于第一种情况，直接将这个素数去乘以所有的已经选好的素数就行了，由于唯一分解定理的存在，一个合数被分解成一系列素数的乘积的结果是唯一的，所以是不可能出现重复的。
对于第二种情况，又由于唯一分解定理(怎么又是你),一个合数存在最小质因子，假设我们选用的数字是i，而i的最小质因子是p[j]，即$i=p[j]\times x$，那么，使用所有小于p[j]的值去和i相乘然后筛除得到的数是不会发生重复的，而对于大于p[j]的素数，假设这个素数为p[j+1]，那么$i\times p[j+1]$又可以展开为$p[j]\times x\times p[j+1]$，而$x\times p[j+1]$在之后的枚举中我们又会枚举到，所以在碰到i的最小质因子之后我们就不需要继续了。
下面来欣赏代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include <iostream>
#include <cstring>
using namespace std;
const int maxn=1e5+10;
bool isprime[maxn];
int p[maxn];
void find(int n)
{
memset(isprime,true,sizeof(isprime));
isprime[1]=false;
int pos=0;
for (int i = 2; i <= n; i++) {
if(isprime[i])p[pos++]=i;
for (int j = 0; j < pos&&i*p[j]<=n; j++) {
isprime[i*p[j]]=false;
if(!(i%p[j]))break;
}
}
}
int main()
{
int n;
cin>>n;
find(n);
for (int i = 1; i <= n; i++) {
if(isprime[i])
cout<<i<<endl;
}
}
|
由于该算法中，$[1,N]$中的每个数都只搜到了一遍，所以该算法的时间复杂度为$O(n)$。
使用筛法可以实现的一些算法
学完如此优美的欧拉筛后，我已经迫不及待的想要实践了，下面列举一些应用场景
找出$[1,N]$中每个数的质因子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| #include<cstdio>
#include<vector>
using namespace std;
const int N = 1e6 + 5;
vector<int> v[N];
void init(){
for(int i = 2; i < N; i ++)
if(v[i].size() == 0)
for(int j = i; j < N; j += i)
v[j].push_back(i);
}
int main(){
init();
}
|
找出$[1,N]$中每个数的因子
1
2
3
4
5
6
7
8
9
10
11
12
13
| #include<cstdio>
#include<vector>
using namespace std;
const int N = 1e6 + 5;
vector<int> v[N];
void init(){
for(int i = 2; i < N; i ++)
for(int j = i; j < N; j += i)
v[j].push_back(i);
}
int main(){
init();
}
|
实现唯一分解定理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include<cstdio>
#include<vector>
using namespace std;
const int N = 1e6 + 5;
vector<int > v[N];
void init(){
int temp;
for(int i = 2; i < N; i ++){
if(v[i].size() == 0){
for(int j = i; j < N; j += i){
temp = j;
while(temp % i == 0){
v[j].push_back(i);
temp /= i;
}
}
}
}
}
int main(){
init();
}
|
参考资料
Ⅰ.关于素数
Ⅱ.欧拉筛法
