1.质因数分解

/* 质因数分解 */
void divide(int n){
    m = 0;
    for(int i =2; i <= sqrt(n); ++ i){
        if(n % i == 0){
            p[++ m] = i, c[m] = 0;
            while(n % i == 0) n/= i, c[m] ++;
        }
    }
    if(n > 1)
        p[++ m] = n, c[m] = 1;
    for(int i = 1; i <= m; ++ i)
        cout << p[i] << " " << c[i] << endl;
}

2.求N的正约数集合 【试除法】

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2010;
int factor[maxn], m = 0;
int main(){
    int n;
    cin >> n;

    for(int i = 1; i * i <= n; ++ i) {
        if(n % i == 0){
            factor[++ m] = i;
            if(i != n / i) factor[++ m] = n / i;
        }
    }
    for(int i = 1; i <= m; ++ i) cout << factor[i] << endl;
}

3.求1~N每个数的正约数集合 【倍数法】

#include <bits/stdc++.h>
using namespace std;
const int maxn = 500010;
vector<int> v[maxn];
int main(){
    int n;
    cin >> n;

    for(int i = 1; i <= n; ++ i)
        for(int j = 1; j <= n / i; ++ j)
            v[i * j].push_back(i);
    for(int i = 1; i <= n; ++ i) {
        for (auto it: v[i]) cout << it << " ";
        cout << endl;
    }
}

4.求最大公约数 【更相减损术】【欧几里得算法】

#include <bits/stdc++.h>

using namespace std;

// 欧几里得算法
int GCD(int a, int b){
    return b ? GCD(b, a % b) : a;
}

//更相减损术求gcd 相比于欧几里得算法求gcd通常用于高精度运算时
int gcd(int a,int b){
    while(a!=b){
        if(a>b) a-=b;
        else b-=a;
    }
    return a;
}

int main(){
    int n, m;
    while(cin >> n >> m)
        cout << gcd(n, m) << " " << GCD(n, m) << endl;
}

5.欧拉函数

#include <bits/stdc++.h>

using namespace std;

int phi(int n) {
    int ans = n;
    for(int i = 2; i <= sqrt(n); ++ i)
        if(n % i == 0) {
            ans = ans / i * (i - 1);
            while(n % i == 0) n /= i;
        }
    if(n > 1) ans = ans / n * (n - 1);
    return ans;
}

int main() {
    int n;
    while(cin >> n) cout << phi(n) << endl;
}

6.求出2~N中每个数的欧拉函数

• Eratosthenes筛法
• 时间复杂度：O(NlogN)

#include <bits/stdc++.h>

using namespace std;

int phi[100005];
void euler(int n){
    for(int i = 2; i <= n; ++ i) phi[i] = i;
    for(int i = 2; i <= n; ++ i)
        if(phi[i] == i)
            for(int j = i; j <= n; j += i)
                phi[j] = phi[j] / i * (i - 1);
}

int main() {
    int n;
    cin >> n;
    euler(n);
    for(int i = 2; i <= n; ++ i)
        cout << i << " " << phi[i] << endl;
    return 0;
}

• 线性筛法
• 时间复杂度：O(N)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000005;
int phi[maxn], v[maxn], prime[maxn], m;

void euler(int n) {
    memset(v, 0, sizeof(v)); // 最小质因子
    m = 0; // 质数数量
    for(int i = 2; i <= n; ++ i) {
        if(v[i] == 0) {
            v[i] = i, prime[++ m] = i;
            phi[i] = i - 1;
        }

        for(int j = 1; j <= m; ++ j) {
            if(prime[j] > v[i] || prime[j] > n / i) break;
            v[i * prime[j]] = prime[j];
            phi[i * prime[j]] = phi[i] * (i % prime[j] ? prime[j] - 1 : prime[j]);
        }
    }
}

int main() {
    int n;
    cin >> n;
    euler(n);
    for (int i = 2; i <= n; ++i)
        cout << i << " " << phi[i] << endl;
    return 0;
}