本文简要讲解简单数论问题：质数和约数相关问题。
包括以下内容： 质数相关： 判定质数、分解质因数、筛质数 ； 约数相关： 求约数、约数个数、约数之和、最大公约数 。
目录 1、质数（素数） 1.1、判定质数 1.2、分解质因数 1.3、筛质数 1.3.1、埃氏筛 1.3.2、欧拉筛（线性筛） 2、约数 2.1、求约数 2.2、求约数个数 2.3、求约数之和 2.4、求两个数的最大公约数 1、质数（素数） 先看一下质数的定义： 质数 （ Prime number ），又称 素数 ，指在大于 1 的 自然数 中，除了1和该数自身外，无法被其他自然数 整除 的数（也可定义为 只有1与该数本身两个正因数的数 ）。
大于1的自然数若不是质数，则称之为 合数 （也称为 合成数 ）。
小于等于1的数既不是质数，也不是合数。
举个例子：2的因子为1和2，所以为质数；6的因子为1、2、3、6，所以为合数；17的因子为1和17，所以为质数。
关于质数，有一些 定理 需要掌握： 质数定理 ：1~n中有 n/logn 个质数； 唯一分解定理 ：任何一个大于1的正整数n都可以 唯一分解成有限个质数的乘积 ，这些数叫n的 质因子 。
还有一些 性质 ： 任何一个大于1的正整数一定存在一个 最小质因子 ； 一个大于1的正整数 N 最多 只包含一个大于 n
\sqrt nn 的 质因子 ，且其幂次一定是1（假设有两个a, b，那么 a*b 一定大于 n ）。
此外，还有一个易混淆的概念： 整除 。
若整数b除以非零整数a，商为 整数 ，且 余数 为零，我们就说 b能被a整除 （或说 a能整除b ），b为被除数，a为除数，即 a|b （“|”是整除符号），读作“a整除b”或“b能被a整除”。
a叫做b的约数（或因数），b叫做a的倍数。
1.1、判定质数 想要判定一个数n是不是质数，首先质数一定是整数，其次小于2的数直接被排除，剩下的数用 试除法 ，也即从2到n-1一个一个试看能不能整除n。
同时注意到一个性质：如果a|b，那么(b/a)|b，即一个数的约数都是成对出现的。
所以其实只需要从2遍历到 n
\sqrt nn 即可。
这样优化让 时间复杂度变为O(n
\sqrt nn)了 。
那么给出函数代码（适用于C/C++）：
//输入一个x，如果是质数就返回真，如果不是就返回假
int is_prime(int x)
{
if (x < 2) return 0;
//这里有其他写法：
//1. i * i <= x 有溢出风险
//2. i <= sqrt(x) 每次都要算sqrt，很慢
//3. i * i <= x 也即 i <= x / i 最优写法
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
return 0;
return 1;
}
1.2、分解质因数 分解n的质因数即把n表示成有限个质数乘积的形式。
只需要 从小到大枚举所有数 即可，枚举到一个n的因子a，就用n连续除以a，直到a不是当前数的因子。
那么这里会有一个问题：为什么不是枚举所有 质因数 呢？
其实只要从小到大枚举所有数，能除的都除掉，就能保证 枚举到的一定是质数 。
简单证明一下：假设枚举到了a，那么a的因子一定是n的因子，所以a的质因子一定是n的质因子，但是2 ~ a-1的质因子已经被除干净了，所以a一定没有2 ~ a-1的质因子了，所以a一定是质数。
此外要注意，除到 最后可能会剩一个大于n
\sqrt nn的质因子 ，这时候特判一下输出即可。
综上，直接给出代码（适用于C/C++）：
//输入一个数，给出分解的质因子+幂次
//比如分解6
//那么输出
//2（质因子） 1（幂次）
//3（质因子） 1（幂次）
void divide(int x)
{
for (int i = 2; i <= x / i; i ++ )
{
if (x % i == 0)
{
//s记录幂次
int s = 0;
//把这个质因子除干净
while (x % i == 0) x /= i, s ++ ;
printf("%d %d\n", i, s);
}
}
//这个大于sqrt(x)的质因子幂次一定是1
if (x > 1) printf("%d 1\n", x);
printf("\n");
}
最坏情况是一个数刚好是2的幂，那么需要进行logn次，所以这个算法的 时间复杂度是O(logn)的 ，但实际平均下来，是要 远小于logn 的，因为一个数很小概率是2的幂。
1.3、筛质数 1.3.1、埃氏筛 要求是给定一个数n，求出1~n之间所有的质数。
正常思路是从2到n一个一个判断，但是这未免太愚蠢了。
所以要进行优化，优化的方法是 每枚举到一个质数，就把它的倍数全部筛掉 。
假设枚举到a且a没有被筛掉，那么a一定没有2 ~ a-1之间的质因子了，因为2 ~ a-1之间所有的质因子的倍数都被筛掉了，那么 a一定是质数 。
因为这个算法是古希腊数学家埃拉托色尼发明的，所以叫埃氏筛。
所以可以直接给出代码了（适用于C/C++）：
//primes数组记录质数，cnt记录下标（也即有几个质数）
int primes[N], cnt;
//st数组记录当前数有没有被筛掉
int st[N];
//输入n，求得1~n之间所有质数，并存入primes数组
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
//如果标记为被筛掉，就跳过当前数
//每个数都会被质因子筛掉，所以如果是合数就直接跳过即可
if (st[i]) continue;
//如果没有被筛，那么就加入质数数组
primes[cnt ++ ] = i;
//用当前数来筛掉所有倍数
for (int j = i + i; j <= n; j += i) st[j] = 1;
}
}
这个算法的 时间复杂度为O(nloglogn) ，基本和O(n)一样。
因为推导过于复杂，这里就不赘述了。
1.3.2、欧拉筛（线性筛） 对于埃氏筛，注意到一个问题：一个数可能被筛多次，比如6会被2筛一次，还会被3筛一次。
那么要优化这个问题，我们使用 欧拉筛（即线性筛） ：让每个数只被 最小质因子 筛掉，这样保证 每个数只被筛一次 ，大大提高了效率。
欧拉筛也是依次枚举每个数，枚举到i的时候，如果i是没被筛，就存入数组；否则就不存入数组。
然后依 次枚举从小到大的质数x ，并筛掉 i * x 。
直到 x 是 i 的最小质因子 。
这样能保证每个数只会被筛一次（参考唯一分解定理）。
下面回答一下难以理解的一些问题： 为什么每个合数是被最小质因子筛掉 ？
筛的时候有两种情况：第一种是 i%x为0 ，那么 此时x一定是i的最小质因子 （因为是从小到大枚举所有质数），那么 x也一定是x * i的最小质因子 ；第二种是 i%x不为0 ，那么 此时x一定小于i的所有质因子 （因为是从小到大枚举所有质数），那么 x一定就是x * i的最小质因子 。
综上所述，每个数都是被最小质因子筛掉的。
为什么每个合数一定会被筛掉 ？
当枚举到某一个 合数i 时，它 一定有一个最小质因子x ，而 i/x一定小于i ，所以它会在 之前枚举到x/i的时候被筛掉 。
为什么到 x 是 i 的最小质因子就停了 ？
因为如果再往下筛，假设 下一个质数是y ，那么 y一定大于x （因为是从小到大枚举质数），但是 y * i的最小质因子是x ，所以 y * i就不是被最小质因子筛掉的了 。
暂停条件不应该加上质数数组的边界吗 ？
如果 i是质数 ，那么 一定会在枚举到i的时候停 ，因为 质数的最小质因子是本身 ；如果 i是合数 ，那 一定会在枚举到i的最小质因子时停 ，i的最小质因子一定小于i，所以 i的最小质因子一定已经加入质数数组了 。
综上，即使不加上越界条件，也会停下。
下面给出代码（适用于C/C++）：
int primes[N], cnt;
int st[N];
//输入n，求得1~n之间所有质数，并存入primes数组
void get_primes(int n)
{
//依次枚举所有数
for (int i = 2; i <= n; i ++ )
{
//如果没被筛掉，就加入素数数组
if (!st[i]) primes[cnt ++ ] = i;
//从小到大枚举所有质数
//既然最后都会停，为什么会加上primes[j] <= n / i?
//因为不加的话，就会筛到需求以外的数，一方面增加了时间复杂度，另一方面可能越界
for (int j = 0; primes[j] <= n / i; j ++ )
{
//筛数
st[primes[j] * i] = 1;
if (i % primes[j] == 0) break;
}
}
}
2、约数 在整除的概念中，已经介绍了约数的概念，这里就不再赘述。
下面直接进入常考问题 2.1、求约数 要求一个数n的约数，也是使用 试除法 ，即从1开始尝试，一直到试到n，如果能整除n，那么就输出。
在质数问题中已经提过： 一个数的约数都是成对出现的 ，所以枚举的时候也只要枚举到 n
\sqrt nn 即可。
只需要特判一下一对约数相等时即可（即约数为 n
\sqrt nn ）。
下面给出代码（适用于C++，C可以用数组存，并自己写排序函数）：
//输入一个数x，返回从小到大存储其约数的vector数组
vector get_divisors(int x)
{
//存储答案
vector res;
for (int i = 1; i <= x / i; i ++ )
{
if (x % i == 0)
{
res.push_back(i);
//如果这对约数不是相等的，就加入一对中的另一个
if (i != x / i) res.push_back(x / i);
}
}
//从小到大排个序
sort(res.begin(), res.end());
return res;
}
2.2、求约数个数 给定一个数，现在要求它的约数个数。
这里要用到一个 公式 ：
简单证明一下 ：
如果题目给出的是让你求一个比较小的数的约数个数，那其实直接试除法就能解决。
但是有这个公式，所以出题人一定会出一些险恶的题目来逼迫你使用这个公式。
下面就来看这样一道题目： 原题 acwing 约数个数 给定 n 个正整数 a
i
a_iai ，请你输出 这些数的乘积 的约数个数，答案对 10 9 +7 取模。
输入格式 第一行包含整数 n。
接下来 n 行，每行包含一个整数 a
i
a_iai 。
输出格式 输出一个整数，表示所给正整数的乘积的约数个数，答案需对 10 9 +7 取模。
数据范围 1≤n≤100, 1≤ a
i
a_iai ≤2×10 9 输入样例 ： 3 2 6 8 输出样例 ： 12 如果用试除法来做，整数直接爆掉了。
那么只能用公式来做了：
#include
#include
#include
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
int main()
{
int n;
cin >> n;
//用stl中的哈希表来存每个质因数以及幂次
unordered_map primes;
while (n -- )
{
int x;
cin >> x;
//分解质因数
for (int i = 2; i <= x / i; i ++ )
while (x % i == 0)
{
x /= i;
primes[i] ++ ;
}
if (x > 1) primes[x] ++ ;
}
LL res = 1;
//套公式
for (auto prime : primes) res = res * (prime.second + 1) % mod;
cout << res << endl;
return 0;
}
2.3、求约数之和 给定一个数，现在要求它的约数之和，要用到另一个 公式 ：
可以简单证明一下：把上式展开，能得到一个多项式，这个多项式包括了 p
1
p_1p1 ~ p
k
p_kpk 所有幂次的排列组合，而n的每个约数又都是 p
1
p_1p1 ~ p
k
p_kpk 一种幂次的排列组合，又根据唯一分解定理，每种排列组合都对应一个不同的数，所以这个多项式就包括了n的所有约数，加在一起也就是约数之和。
具体大家可以推导一下，证明非常容易。
同样，出题人会出一些阴险的题目来逼迫你使用这个公式： 原题 acwing 约数之和 给定 n 个正整数 a
i
a_iai ，请你输出 这些数的乘积 的约数之和，答案对 10 9 +7 取模。
输入格式 第一行包含整数 n。
接下来 n 行，每行包含一个整数 a
i
a_iai 。
输出格式 输出一个整数，表示所给正整数的乘积的约数之和，答案需对 10 9 +7 取模。
数据范围 1≤n≤100, 1≤ a
i
a_iai ≤2×10 9 输入样例 ： 3 2 6 8 输出样例 ： 252
#include
#include
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
int main()
{
int n;
cin >> n;
unordered_map primes;
while (n -- )
{
int x;
cin >> x;
for (int i = 2; i <= x / i; i ++ )
while (x % i == 0)
{
primes[i] ++ ;
x /= i;
}
if (x > 1) primes[x] ++ ;
}
LL res = 1;
//套公式
for (auto prime : primes)
{
LL a = prime.first, b = prime.second;
LL t = 1;
//求一个数的连续幂次多项式有很多种方法，这里是一个简答的方法
//如果不懂可以自己用纸和笔模拟一下
while (b -- ) t = (t * a + 1) % mod;
res = res * t % mod;
}
cout << res << endl;
return 0;
}
2.4、求两个数的最大公约数 求两个数的最大公约数一般使用 欧几里得算法 （也叫 辗转相除法 ）。
首先要掌握一个 性质 ： 如果d|a，d|b，那么d|(ax+by)，（x,y是整数） a和b的最大公约数 等于 b和a mod b的最大公约数 。
对于性质2，简单证明一下：
那么就可以给出代码了（适用于C/C++）：
//输入a和b，返回其最大公约数
int gcd(int a, int b)
{
//如果b不是0，那么就返回b,和a % b的最大公约数
//如果b是0，那就返回a，因为0能被任何数整除
return b ? gcd(b, a % b) : a;
}