质数
概述
质数
(prime number，又称素数)：
指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数（也可定义为只有1与该数本身两个
正因数
的数）。
否则称为
合数
（又称合成数）。
注
：
1既不是质数也不是合数，2是最小的质数且是唯一的偶质数
质数判断
试除法
O
(
n
)
O(\sqrt{n})
O
(
n
)
思想
：根据定义，可以从2~n-1依次试除，判断n是否有约数（若有则n不是质数）
优化
：假设
d
d
d
可以整除
n
n
n
，那么它们的商
n
/
d
n/d
n
/
d
也能整除
n
n
n
。假设两者的关系是
d
<
=
n
/
d
d<=n/d
d
<=
n
/
d
，即
d
2
<
=
n
d^2<=n
d
2
<=
n
，那么
d
<
=
n
d<=\sqrt n
d
<=
n
。所以每次判断只需要判断到
n
\sqrt{n}
n
即可。
时间复杂度
：优化后时间复杂度为
O
(
n
)
O(\sqrt{n})
O
(
n
)
bool isprime(int n)
{
for (int i = 2; i <= n / i; i++)//也有的会写为i*i<=n，不过存在溢出风险，使其变为负数，影响结果判断。最好写为i<=n/i，不存在溢出风险
if (n % i == 0) return false;
return true;
}
质数筛法
朴素筛法
O
(
n
n
)
O(n\sqrt{n})
O
(
n
n
)
背景
：质数相关的问题，如果用传统的遍历法的话，一次只能求解一个（
O
(
n
)
O(\sqrt n)
O
(
n
)
）
过程：
试除法将素数保存下来即可
int prime[N], cnt;
for (int i = 2; i <= 100; i++)
if (isprime(i))prime[++cnt] = i;
埃氏筛法
O
(
n
l
o
g
n
)
O(nlogn)
O
(
n
l
o
g
n
)
思想
：从2开始任何整数 x 的倍数都不是质数。
过程
：初始时，先假设所有数都是质数，从2开始枚举，并标记每个数的倍数为合数，若枚举到一个数未被标记，说明该数就是质数。
时间复杂度
：
O
(
n
l
o
g
n
)
O(nlogn)
O
(
n
l
o
g
n
)
int prime[N], cnt;
bool st[N];
void GetPrimes(int n)
{
memset(st, true, sizeof(st));
for (int i = 2; i <= n; i++)
{
if (st[i]) prime[++cnt] = i;
for (int j = i + i; j <= n; j += i) st[j] = false;//筛掉该数的倍数
}
}
埃氏筛相关
：
1、埃拉托斯特尼选筛法，简称埃氏筛，也有人称素数筛。
2、
算术基本定理
(又称唯一分解定理），任何一个大于1的自然数N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积。也就是说，合数一定是某个质数的倍数。
优化
：埃氏筛法是不管是合数还是质数都直接筛，会有许多重复的操作。根据算术基本定理，只筛掉质数的倍数。
时间复杂度
：
O
(
n
l
o
g
l
o
g
n
)
O(nloglogn)
O
(
n
l
o
g
l
o
g
n
)
该算法实现简单，效率已经非常接近与线性（n <= 10
6
）
int prime[N], cnt;
bool st[N];
void GetPrimes(int n)
{
memset(st, true, sizeof(st));
for (int i = 2; i <= n; i++)
{
if (!st[i])continue;//合数
prime[++cnt] = i;
for (int j = i + i; j <= n; j += i) st[j] = false;//筛掉质数倍数
//遍历范围内的i的倍数 可从i*i开始，可以减少重复筛选（
}
}
线性筛法
O
(
n
)
O(n)
O
(
n
)
欧拉筛，也被称作线性筛
背景
：埃氏筛中一些合数被重复筛选（如：6会被2和3筛选），这样会有许多重复操作
思想
：在埃氏筛法的基础上，让每个合数只被它的最小质因子筛选一次，以达到不重复的目的
时间复杂度
：
O
(
n
)
O(n)
O
(
n
)
当数据规模在
10
6
时，线性筛法和埃式筛法效率差不多，但是当数据规模在
10
7
时线性筛法的效率大约是埃式筛法
2倍
。
int prime[N], cnt;
bool st[N];
void GetPrimes(int n)
{
memset(st, true, sizeof(st));
for (int i = 2; i <= n; i++)
{
if (st[i])prime[++cnt] = i;
for (int j = 1; prime[j] <= n / i; j++)
{
st[prime[j] * i] = false;
//(prime[j] * i)为要筛掉的合数
//(prime[j] * i)的最小质因数 = min(prime[j]的最小质因数, i的最小质因数)
//质数prime[j]的最小质因数是它本身
//当i% prime[j] != 0时，i的最小质因数>prime[j]，所以(prime[j] * i)的最小质因数 = prime[j]
//当i% prime[j] == 0时，i的最小质因数=prime[j]，所以(prime[j] * i)的最小质因数 = prime[j]
if (i % prime[j] == 0)break;
//若i% prime[j] == 0后继续枚举质数表，那么prime[j+1]>prime[j]，即prime[j+1]不是i的最小质因子
//自然prime[j+1]不是(prime[j]*i)的最小质因子
}
}
}