acwing数学知识（一）质数 约数

本文主要是介绍acwing数学知识（一）质数 约数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.质数——筛质数

题目：给定一个正整数n，请你求出1~n中质数的个数。

（1）朴素筛法O(nlogn)

算法核心：把每个数的所有倍数筛掉

调和级数：1 + 1/2 + 1/3 +…+ 1/n = lnn + c(c欧拉常数=0.577)

算法时间复杂度：最外层遍历整个数组是n（其实不用管，只用看内部总次数即可），内部循环总次数是n/2,n/3,n/4…1，累加得n(1/2 + 1/3 + 1/4 +…+1/n)=nlnn=nlogn

void get_prime(int x)
{for (int i = 2; i <= n; i ++ ){if (!st[i]) primes[cnt ++] = i;for(int j = i + i ; j <=  n ; j += i) st[j] = true;}
}

（2）埃式筛法O(nloglogn)

算法核心：把每个质数的所有倍数筛掉

质数定理：1~n中由n/logn个质数

算法时间复杂度：由（1）可得：O（nlonglongn）当数据不是足够大时与O(n)接近

void get_primes(int n)
{for (int i = 2; i <= n; i ++ ){if (st[i]) continue; //st如果是true 说明被筛过，那么它的倍数肯定被筛过，所以直接跳过//接下来对该质数的所有倍数进行筛选primes[cnt ++ ] = i;for (int j = i + i; j <= n; j += i)st[j] = true;}
}

（3）线性筛法O(n)

算法核心：x只会被它的最小质因数筛去，即每个数字只被筛选一次，因此是线性的n。

证明每个x都能被筛掉：
对于一个合数x，x一定存在一个最小质因子，假设pj是x 的最小质因子，当i枚举到x/pj时，x就被筛了，因为x只有一个最小质因数，因此每个数字只被筛选一次。

算法时间复杂杂度：因为每个数只被筛过一次，因此为O(n)

void get_prime(int x)
{for(int i = 2 ; i <= x ; i++){if(!st[i]) primes[cnt ++] = i;/**for循环判断语句中不需要j<cnt。分两种情况。1.i为合数，当primes[j]取到i的最小质因子时就break 此时 j<cnt2.i为质数，当primes[j]的值和i相等时就break 此时j == cnt-1**/for(int j = 0 ; primes[j] <= x / i ; j++){										st[primes[j] * i] = true; //筛去primes[j]的倍数/*针对st[primes[j] * i] = true;本质上分两种情况1.i%pj == 0, 因为primes[j]是顺序遍历，因此当当一次模为零时，primes[j]一定为i的最小质因子，primes[j]也一定为primes[j]*i的最小质因子2.i%pj != 0, 同样因为primes[j]是顺序遍历，primes[j]一定小于i的所有质因子所以primes[j]也一定为primes[j]*i最小质因子*/if(i % primes[j] == 0) break;//当primes[j]是i的最小质因数时break（为了  			   //遵守算法的核心，避免重复的筛选）。如果继续用primes[j+1]去筛选，此时，//primes[j+1]大于i的最小质因子，那么也同样不是primes[j+1]*i的最小质因子}}
}

2.约数

根据分摊分析，当数据最够多时，每个数的约数平均为logn个。
(第一个数是n个数的约数 ， 第二个数是n/2个数的约数 ， 以此类推第n个数是n/n个数的约数。
累加得n(1/1+1/2+1/3+…+1/n)=n(lnn+c)≈nlogn)

（1）试除法O(sqrt(n))

思路：从小到大枚举较小的约数即可

vector<int> get_divisors(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;
}

（2）约数个数

题目：给定n个正整数ai，请你输出这些数的乘积的约数个数，答案对109+7取模。

算法思想：
基于算数基本定理：N = p₁^a1 * p₂^a2 * … * p_k^ak
N的任意一项约数可以写成 d = q₁^b1+q₂^b2+…+q_k^bk

不同的b数组组合而成的约数d是不同（即因式分解不同）
同理不同的a数组组合而成的N也是不同的，

而a1有a1+1种选法，a2有a2+1种选法…ak有ak+1种选法
因此约数个数：(a₁+1)(a₁+1)(a₃+1)…(a_k+1)

#include <iostream>
#include <unordered_map>using namespace std;typedef long long ll;const int P = 1e9 + 7;
int main()
{unordered_map<int , int> primes; //利用哈希表存储int n;cin >> n; 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 ans = 1;for(auto p : primes) //迭代一次，套用公式即可ans = ans * (p.second + 1) % P;  cout << ans << endl; return 0;
}

（3）约数之和

同样的某个数N可以展开为 N = p₁^a1 * p₂^a2 * … * p_k^ak

约数之和为：(p₁⁰+p₁¹+p₁²+…+p₁^a1) * (p₂⁰+p₂¹+p₂²+…+p₂^a2) * …* (p_k⁰+``p_k¹+p_k²+…+p_k^ak)
即排列问题，展开后就是每一个约数，且都不相等

//求质因数与上方代码相同
for(auto t : primes){int p = t.first , q = t.second;ll res = 1;while(q--)  res = (res * p + 1) % P; //这里有一个小技巧><ans = ans * res % P;}

(4) 最大公约数

(greast common divisor简称“gcd”)

递归版辗转相除法(欧几里得算法)：核心是gcd(a , b) = gcd(b , a % b)
原理:
由基本定理得：当d能分别整除a,b时，d就能整除xa+yb。
显然a % b = a - c * b(其中c=a/b)。
即证：(a , b) = (b , a - c * b)
记d=(a,b)，则d|a，d|b,所以根据基本定理得d|a-cb,所以d=gcd(b , a-cb)
记d=(b , a-cb) , 则d|b , d|a-cb ,所以根据基本定理得：d|(cb)+(a-cb) 即a|b ，所以d=(a , b)
所以(a , b) = (b , a-c*b)成立，说明(a,b)的公约数就是(b , a - c * b)的公约数，所以等号两边的最大公约数相同。
不断地辗转相除直到第二个参数为0，因为0模上任何一个非零的整数都是0，所以任何一个数都可以看作是0的约数，而b的最大约数是b，那取交集后，gcd(b,0)当然是b。
所以gcd(a , b) = gcd(b , a % b)成立

//核心代码，非常非常简单
int gcd(int a , int b)
{return b ? gcd(b , a % b) : a;
}

这篇关于acwing数学知识（一）质数 约数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---