文章目录
求素数
素数是数学的一大分支，也是编程中数学解题的一大基础。因此，求素数是一项基础知识。
1.暴力（傻瓜算法）
这是最没用的算法，时间复杂度太高：枚举 n n n以内的每一个数，再用试除法判断该数是否为素数。
//Maxn 为数组q的大小。
bool check(int n)
{
for(int i = 0 ; i * i < n ; i ++)
if(n % i == 0)
return false;
return true;
}//试除法
void make_q(int n)
{
for(int i = 2 ;i <= n ; i++)//1和0既不是质数也不是合数，应单独判断
if(check(i))
q[i] = true
}
2.Eratosthenes筛法
最常用的素数筛，其原理是每枚举到一个素数就将其倍数全标记为合数，那么没有统计到的就是素数。计算到 n \sqrt{n} n 时就可以筛出小于 n n n的所有素数。
code
bool q[Size];//Size为n的最大值。
void make_q(int n)
{
q[1] = false;
q[0] = false;
for(int i = 2 ; i * i <= n ; i++)//初始化。
q = true;
for(int i = 2 ; i * i <= n ; i++)
{
for(int j = i * i ; j <= n ; j += j)
{
q[j] = false;
}
}
}
但在这种情况下还是会有大量点被重复标记，所以可以选择只筛素数的倍数，这与筛所有数的倍数是等效的（参照算术基本定理）。
bool q[Size];
void make_q(int n)
{
q[0] = false;
q[1] = false;
for(int i = 2 ; i * i <= n ; i++)
{
if(q[i])
{
for(int j = i * i ; j < n ; j++)
{
q[j] = true;
}
}
}
}
复杂度 O ( n × log log n ) O(n\times\log{\log{n}}) O(n×loglogn)
3.线性筛法（欧拉筛）
埃氏筛虽然复杂度接近线性但还是有一定偏差，所以欧拉筛应运而生欧拉筛是一种线性复杂度的素数筛算法原理基础是算术基本定理。基于算术基本定理，每一个数一定可以表示为若干个质数之积(质数除外)。所以每一个数的最小质因子是确定的，因此我们可以用最小质因子来标记每一个数，对于每一个数
i
i
i而言，对于每一个小于
i
i
i的最小质因子的质数
j
j
j都可以筛掉
i
×
j
i\times j
i×j这个数。且对于不同的
i
i
i而言满足
i
×
j
i\times j
i×j不重不漏。
举例：一开始枚举
2
2
2时将
2
2
2标记为质数并将其最小质因数定为
2
2
2,然后将
2
×
2
2\times2
2×2的最小质因数标记为
2
2
2，接下来枚举
3
3
3时重复上述操作但当标记时是先将小于
3
3
3的
2
2
2与之相乘得到的
6
6
6的最小质因子标记为
2
2
2然后再算
3
×
3
3\times3
3×3的最小质因子。像这样每次将小于等于该数的最小质因子的数与这个数本身相乘，就能做到不重不漏。
具体看代码
code
int f[Size], q[Size];
void make_q(int n)
{
int top = 0;
for(int i = 2 ; i <= n ; i++)
{
if(!f[i])
{
f[i] = i;
q[top++] = i;
}
for(int j = 0 ; p[j] <= f[i] && j < top ; j++)
{
f[i * p[j]] = p[j];
if(p[j] > n / i)//当所枚举到的质数与当前数的积大于n是退出。
break;
}
}
}
复杂度 O ( n ) O(n) O(n)。
质因子分解
对于不同的题，有时候将其有规律地用其他的数表示出来会更易于解题或者优化，而基于算术基本定理的质因子分解就是最方便的方法之一。
依据算术基本定理，每一个数都可以分解成有限的质数的成积。因此，我们可以将一个数唯一地分解为若干个质数之积，这若干个质数就是该数的质因子分解结果。
由于每个数
n
n
n可以被唯一的一组质数表示，所以可以从小到大枚举该数的因子
i
i
i，对每一个因子， 都将
n
n
n除去这个因数
i
i
i,直到
i
i
i不再是当前
n
n
n的因子，因为合数可以表示为若干个质数之积，所以每一个去除的
i
i
i一定是该数的质因子。
int qn[Size][2]//Size是该数的质因子个数范围,第二维限制储存质因子和它的数目。
void devide(int n)
{
int tot = 0;
for(int i = 2 ; i <= n ; i++)//因为n可能本身就是素数所以i枚举到n.
{
if(n % i == 0)
qn[tot][0] = i;
while(n % i == 0)
{
n /= i;
qn[tot][1]++;
}
}
}
复杂度最差
O
(
n
)
O(n)
O(n)
由于每一个数的质因子要么是他自己，要么不大于他开根，所以可以优化为下列代码
int qn[Size][2]//Size是该数的质因子个数范围,第二维限制储存质因子和它的数目。
void devide(int n)
{
int tot = 0;
int temp = sqrt(n);//sqrt()来自#include<cmath>库
for(int i = 2 ; i <= temp ; i++)
{
if(n % i == 0)
qn[tot][0] = i;
while(n % i == 0)
{
n /= i;
qn[tot][1]++;
}
}
if(n > 1)//处理n是质数的情况
{
qn[tot][0] = n;
qn[tot][1] = 1;
}
}
此时的复杂度已经降到了严格的 O ( log 2 n ) O(\log_{_{2}}n) O(log2n)，然而还是有多余的扫描，我们只需要查找质因子即可，所以可以先用素数筛求出素数，再分解质因子，如下。
int f[Size], q[Size] , qn[Size][2];
int top = 0;
void make_q(int n)
{
for(int i = 2 ; i <= n ; i++)
{
if(!f[i])
{
f[i] = i;
q[top++] = i;
}
for(int j = 0 ; p[j] <= f[i] && j < top ; j++)
{
f[i * p[j]] = p[j];
if(p[j] > n / i)//当所枚举到的质数与当前数的积大于n是退出。
break;
}
}
}
void devide(int n)
{
int tot = 0;
int temp = sqrt(n);//sqrt()来自#include<cmath>库
for(int i = 0; i < top ; i++)
{
if(n % q[i] == 0)
qn[tot][0] = i;
while(n % q[i] == 0)
{
n /= q[i];
qn[tot][1]++;
}
}
if(n > 1)//处理n是质数的情况
{
qn[tot][0] = n;
qn[tot][1] = 1;
}
}
该算法基本上是 O ( m ) O(m) O(m)了 ， m m m为质因子个数。
作者留言
本博客会一直更新（只要我想到怎么补充了）。