质数
- 对所有的大于1的自然数字,定义了【质数/合数】这一概念。对于所有小于等于1的自然数,没有这个概念,它们既不是质数也不是合数。
- 质数的定义:对于大于1的自然数,如果这个数的约数只包含1和它本身,则这个数被称为质数,或者素数
质数的判定
试除法O(sqrt(n))
对于一个数n,从2枚举到n-1,若有数能够整除n,则说明除了1和n本身,n还有其他约数,则n不是质数;否则,n是质数
优化:由于一个数的约数都是成对出现的。比如12的一组约数是3,4,另一组约数是2,6。则我们只需要枚举较小的那一个约数即可
我们用\(d|n\)来表示d整除n,比如\(3∣12\),只要满足\(d|n\),则一定有\(\frac{n}{d}|n\),因为约数总是成对出现的,我们只需要枚举小的那部分数即可,令\(d ≤ \frac{n}{d}\),即,\(d ≤ \sqrt{n}\),因此对于n,只枚举2到\(\sqrt{n}\)即可。
代码模板
bool is_prime(int n) {
if(n < 2) return false;
for(int i = 2; i <= n / i; i++) {
if(n % i == 0) return false;
}
return true;
}
注意有一个细节,for循环的结束条件,推荐写成i <= n / i
。有的人可能会写成i <= sqrt(n)
,这样每次循环都会执行一次sqrt函数,而这个函数是有一定时间复杂度的。而有的人可能会写成i * i <= n
,这样当i很大的时候(比如i比较接近int的最大值时),i * i
可能会溢出,从而导致结果错误。
分解质因数
朴素思路
还是采用试除法:
对于一个整数 n 总能写成如下形式:
\(N = P_{1} ^ {k_{1}} \times P_{2} ^ {k_{2}} \times \dots \times P_{n} ^ {k_{n}}\),其中\(P_{1} \dots P_{n}\) 都是质数,\(k_{1} \dots k_{n}\) 都是大于等于0的正整数。
对于一个数求解质因数的过程:从2到n,枚举所有数,依次判断是否能够整除 n 即可。
求质因数分解,为什么枚举所有数,而不是枚举所有质数,万一枚举到合数怎么办?解释:枚举数时,对于每个能整除 n 的数 i,先把这个数除干净了,再继续枚举后面的数,这样能保证,后续再遇到能整除的数,一定是质数而不是合数。
例如:求180的质因数分解
- i = 2 n = 180 / 2 = 90 / 2 = 45
- i = 3 n = 45 / 3 = 15 / 3 = 5
- i = 4 当i是合数时,i 一定不能整除 n 。如果 4 能整除 n 那么 2 一定还能整除 n,就是在 i = 2的时候没有除干净,而我们对于每个除数都是除干净的,因此产生矛盾。
- i = 5 n = 5 / 5 = 1
void divide(int n) {
for(int i = 2; i <= n; i++) {
if(n % i == 0) {
int s = 0;
while(n % i == 0) {
s++;
n /= i;
}
printf("%d %d\n", i, s);
}
}
}
优化 O(sqrt(n))
性质:n中只包含一个大于\(\sqrt{n}\)的质因子,很好证明,如果中包含两个大于\(\sqrt{n}\)的质因子,那么乘起来就大于n了
因此,在枚举的时候可以先把2到\(\sqrt{n}\)的质因子枚举出来,如果最后处理完n > 1,那么这个数就是那个大于\(\sqrt{n}\)的质因子,单独处理一下就可以
void divide(int n) {
for(int i = 2; i <= n / i; i++) {
if(n % i == 0) {
int s = 0;
while(n % i == 0) {
s++;
n /= i;
}
printf("%d %d\n", i, s);
}
}
if (n > 1) printf("%d %d", n, 1);
}
筛质数
朴素筛法
将2到n全部数放在一个集合中,遍历2到n,删除集合中这个数的倍数。最后集合中剩下的数就是质数。
解释:如果一个数p没有被删掉,那么说明在2到p-1之间的所有数,p都不是其倍数,即2到p-1之间,不存在p的约数。故p一定是质数。
时间复杂度:\(\frac{n}{2} + \frac{n}{3} + \dots +\frac{n}{n} = n\ln_{}{n} < n\log_{2}{n}\)故,朴素思路筛选质数的时间复杂度大约为O(nlogn)
埃氏筛法
int primes[N],cnt;
bool st[N];
void get_primes(int n) {
for(int i = 2; i <= n; i++) {
if(!st[i]) ptimes[ctn++] = i; // i是质数
for(int j = i; j <= n; j += i) st[j] = true; // 删数
}
}
其实不需要把全部数的倍数删掉,而只需要删除质数的倍数即可。
对于一个数p,判断其是否是质数,其实不需要把2到p-1全部数的倍数删一遍,只要删掉2到p-1之间的质数的倍数即可。因为,若p不是个质数,则其在2到p-1之间,一定有质因数,只需要删除其质因数的倍数,则p就能够被删掉。埃氏筛法筛选质数的时间复杂度大约为O(nloglogn)
int primes[N],cnt;
bool st[N];
void get_primes(int n) {
for(int i = 2; i <= n; i++) {
if(!st[i]) {
ptimes[cnt++] = i; // i是质数
for(int j = i; j <= n; j += i) st[j] = true; // 删数
}
}
}
线性筛法(欧拉筛)
大体思路和埃氏筛法一样,将合数用他的某个因数筛掉,其性能要优于埃氏筛法(在\(10^{6}\)下两个算法差不多,在\(10^{7}\)下线性筛法大概快一倍)核心思路是:对于某一个合数n,其只会被自己的最小质因子给筛掉
int primes[N],cnt;
bool st[N];
void get_primes(int n) {
for(int i = 2; i <= n; i++) {
if(!st[i]) ptimes[cnt++] = i; // i是质数
for (int j = 0; primes[j] <= n / i; j++) {
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
对上面的代码解释如下:
用pj来表示primes[j]
- 当
i % pj == 0
时:pj 一定是 i 的最小质因子,因为我们是从小到大枚举质数的,首先遇到的满足i % p j == 0
的,pj 一定是 i 的最小质因子,并且pj 一定是\(pj \times\) i的最小质因子。比如,\(15 = 3 \times 5\),15的最小质因子是3,则15的倍数中最小的数,且最小质因子同样是3的,一定是给15乘以一个最小质因子3,即45。 - 当
i % pj != 0
时:pj 一定不是 i 的质因子,并且由于是从小到大枚举质数的,那么 pj 一定小于 i 的全部质因子。那么 pj 就一定是 \(pj \times i\) 的最小质因子。
因此,则无论哪种情况,pj都一定是 \(pj \times i\) 的最小质因子。
如何保证所有合数都被筛掉, 对于一个合数x,当枚举到 x / pj 时,就会被删掉,因此每个合数都会被筛掉
线性筛法保证了,每个合数,都是被其最小质因子给删掉的,且只会被删一次
约数
求一个数的所有约数O(sqrt(n))
利用试除法求一个数的所有约数,思路和判断和质数的判定类似
约数都是成对出现的,只需要枚举1到\(\sqrt{n}\)即可
vector<int> get_dividers(int x) {
vector<int> 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;
}
约数个数/约数之和
将一个数N分解质因数为\(N=P_{1} ^{k_1} \times P_{2} ^{k_2} \times P_{3} ^{k_3} \dots \times P_{n} ^{k_n}\)
定理1:约数的个数为\((k_{1} + 1) \times (k_{2} + 1) \times \dots \times (k_{n} + 1)\)
定理2:所有约数之和为\((P_{1}^{0} + P_{1} ^ {1} + \dots + P_{1} ^{k_1}) \times (P_{2}^{0} + P_{2} ^ {1} + \dots + P_{2} ^{k_2}) \times \dots \times (P_{n}^{0} + P_{n} ^ {1} + \dots + P_{n} ^{k_n})\)
最大公约数(欧几里得算法/辗转相除法)
性质:gcd(a,b) == gcd(b, a % b)
证明:假设\(`a`\)和\(`b`\) 的最大公约数为\(`k`\) ,则可以写成\(`a = a_{k} \times k\),\(b = b_{k} \times k\),那么$a_{k}$ 和 $b_{k}$一定是互质的,由于公式需要
a mod b ,则把$
a$写成 $
a = c \times b + d$,即
a mod b = d,带入$
b = b_{k} \times k$,则$
a = c \times b_{k} \times k + d = a_{k} \times k$,消去$
k$得到$
c \times b_{k} + \frac{d}{k} = a_{k}$ ,因为$
a_{k}$是整数,则$
\frac{d}{k}$也是整数 ,因此$
d$是$
k$的倍数,但是
gcd(b,d)一定是$
k`$吗?
反证法:假设gcd(b,d)$=k^{’} > k$
,令\(`b = b_{k}^{’} \times k^{’}`\),\(`d = d_{k}^{’} \times k^{’}`\),带入到\(`a = c \times b + d`\) ,得到\(`a = c \times b_{k}^{’} \times k^{’} + d_{k}^{’} \times k^{’}`\),那么\(`a`\)和\(`b`\) 的最大公约数为就会等于\(`k^{’}`\),产生矛盾。得证,gcd(a,b) == gcd(b, a % b)
代码模板
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
标签:约数,int,质数,times,枚举,数学知识,pj,第四章
From: https://www.cnblogs.com/chenjq12/p/17115042.html