质数与约数

质数

// 判断质数 试除法
#include <cmath>
bool is_prime(int n){
    if(n < 2) return false;
    for(int i = 2; i <= sqrt(n); i ++)
    // for(int i = 2; i <= n / i; i ++)
        if(n % i == 0) return false;
    return true;
}

// 分解质因数
void divide(int n){
    for(int i = 2; i <= n; i ++){
        if(n % i == 0){
            int s = 0; // s 是质因子的次数
            while(n % i == 0){
                n /= i;
                s ++;
            }
            cout << i << s;
        }
    }
}
// n 中至多只包含一个大于 sqrt(n) 的质因子
void divide(int n){ // 优化
    for(int i = 2; i <= n / i; i ++){ // sqrt(n)
        if(n % i == 0){
            int s = 0; // s 是质因子的次数
            while(n % i == 0){
                n /= i;
                s ++;
            }
            cout << i << s << endl;
        }
    }
    if(n > 1) cout << n << 1 << endl;
}

质数定理：1~n 之间大约有 n / ln n 个质数。

// 朴素筛法
#include <iostream>
#include <cmath>
using namespace std;
const int N = 1000010;
int primes[N], st[N], cnt;
void get_primes(int n){
    for(int i = 2; i <= n; i ++){
        if(!st[i]) primes[cnt ++] = i;
        for(int j = i + i; j <= n; j += i) st[j] = 1; // 不管是不是是质数，都筛掉后面它的倍数
    }
}
int main(){
    int n; cin >> n;
    get_primes(n);
    cout << cnt << endl;
    for(int i = 0; i < sqrt(n); i ++) if(primes[i]) cout << primes[i] << " ";
}

// 优化筛法 埃氏筛法
void get_primes(int n){ // O(n log log n)
    for(int i = 2; i <= n; i ++){
        if(!st[i]) {
            primes[cnt ++] = i;
        	for(int j = i + i; j <= n; j += i) st[j] = 1; // 只筛质数的倍数
        }
    }
}
// 由小到大扫描每个数 i, 对于小于 i^2 的 i 的倍数在扫描更小的数时已经被标记过了, 所以只需要从 x^2 开始标记, x^2, x(x+1), x(x+2)...
void get_primes(int n){ // O(n log log n)
    for(int i = 2; i <= n; i ++){
        if(!st[i]) {
            primes[cnt ++] = i;
        	for(int j = i; j <= n / i; j ++) st[i * j] = 1;
        }
    }
}

// 线性筛法：只筛最小质因子的倍数，不会重复筛
void get_primes(int n){ // O(n log log n)
    for(int i = 2; i <= n; i ++){
        if(!st[i]) primes[cnt ++] = i;
        for(int j = 0; primes[j] <= n / i; j ++) { // 变形一下得到primes[j]*i<=n，筛掉所有小于 n 的质数的倍数
            st[primes[j] * i] = 1; // 用最小质因子去筛合数
            // 1)当 i % primes[j] != 0 时,说明二者也是互素的, primes[j] 必是 primes[j] * i 的最小质因子
            // 2)当 i % primes[j] ==0 时,说明 i 的最小质因子是 primes[j],之后接着用 st[primes[j+1]*i]=1 去筛合数时，就不是用最小质因子去更新了,因为i有最小质因子primes[j]<primes[j+1],此时的primes[j+1]不是primes[j+1]*i的最小质因子，此时就应该退出循环，避免重复进行筛选。
            if(i % primes[j] == 0) break;
        } 
    }
}

约数

// 试除法
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> get_divisors(int n){
    vector<int>res;
    for(int i = 1; i <= n / i; i ++){
        if(n % i == 0){
            res.push_back(i);
            if(i != n / i) res.push_back(n / i);
        }
    }
    sort(res.begin(), res.end());
    return res;
}

约数个数：若质因数分解 $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$ ，则约数个数 $(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_k+1)$ 。

const int mod = 1e9 +7;
typedef long long ll;
unordered_map<int, int>primes;
int main(){
    int m; cin >> m;
	while(m --){
    	int n; cin >> n;
    	for(int i = 2; i <= n / i; i ++){
        	while(n % i == 0){
            	n /= i;
            	primes[i] ++;
        	}
    	}
        if(n > 1) primes[n] ++;
	}
    ll res = 1;
    for(auto prime: primes)res = res * (prime.second + 1) % mod;
    cout << res;
}

约数之和：$(p_1^0+p_1^1+\cdots+p_1^{\alpha_1})(p_1^0+p_1^1+\cdots+p_1^{\alpha_2})\cdots (p_1^0+p_1^1+\cdots+p_1^{\alpha_k})$ 约数是乘积的形式，展开即可。

mod = 1e9 +7;
unordered_map<int, int>primes;
int main(){
	while(m --){
    	int n; cin >> n;
    	for(int i = 2; i <= n / i; i ++){
        	while(x % i == 0){
            	x /= i;
            	primes[i] ++;
        	}
    	}
        if(n > 1) primes[n] ++;
	}
    ll res = 1;
    for(auto prime: primes){
        int p = prime.first, a = prime.second;
        ll t = 1;
        while(a --) t = (t * p + 1) % mod; // y = a[n], while(n --) y = (y * x + a[n-1]) //多项式秦九韶
        res = res * t % mod;
    }
    cout << res;
}

最大公约数

$(a, b)=(b,a\% b)$

$(a,0)=a$

// 辗转相除法(欧几里得算法) 
int gcd(int a, int b){
    while(b){
        int tmp = b;
        b = a % b;
        a = tmp;
    }
    return a;
}
int gcd(int a, int b){
    return b ? gcd(b, a % b) : a;
}

Q.E.D.