试除法判定质数

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
bool is_prime(int x){
    if(x < 2) return false;
    for(int i = 2; i <= x / i; i ++)
        if(x % i == 0){
            return false;
        }
    return true;
}
int main()
{
    int n;
    cin >> n;
    while(n --){
        int x;
        cin >> x;
        if(is_prime(x)) puts("Yes");
        else puts("No");
    }
    return 0;
}

分解质因数

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
void divide(int x){
    for(int i = 2; i <= x/i; i ++){
        int cnt = 0;
        while(x % i == 0){
            cnt ++;
            x /= i;
        }
        if(cnt) printf("%d %d\n", i, cnt);
    }
    if(x > 1) printf("%d %d\n", x, 1);
    puts("");
}
int main()
{
    int n;
    cin >> n;
    while(n --){
        int x;
        cin >> x;
        divide(x);
    }
    return 0;
}

朴素筛法

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000010;
int primes[N], cnt;
bool st[N];
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] = true;
        }
    }
}
int main()
{
    int n;
    cin >> n;
    get_primes(n);

    cout << cnt << endl;

    return 0;
}

线性筛法

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000010;
int primes[N], cnt;
bool st[N];
void get_primes(int n){
    for(int i = 2; i <= n; i ++){
        if(!st[i]) primes[cnt ++] = i;

        for(int j = 0; primes[j] <= n/i; j ++){
            st[primes[j]*i] = true;
            if(i % primes[j] == 0) break;
        }

    }
}
int main()
{
    int n;
    cin >> n;
    get_primes(n);

    cout << cnt << endl;

    return 0;
}

试除法判定约数

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

void get(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());
    for(auto t: res) printf("%d ", t);
    puts("");
}
int main()
{
    int n;
    cin >> n;
    while(n --){
        int x;
        cin >> x;
        get(x);
    }

    return 0;
}

约数个数

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int mod = 1e9 + 7;

int main()
{
    unordered_map<int, int> hash;
    long long res = 1;
    int n;
    cin >> n;
    while(n --){
        int x;
        cin >> x ;
        for(int i = 2; i <= x/i; i ++){
            while(x % i == 0) hash[i] ++, x /= i;
        }
        if(x > 1) hash[x] ++;
    }
    for(auto t: hash){
        int p = t.first, a = t.second;

        res = res * (a + 1) % mod;
    }
    cout << res << endl;

    return 0;
}

约数之和

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;
const int mod = 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 res = 1;
    for(auto it: primes){
        int p = it.first, a = it.second;
        LL t = 1;
        while(a --) t = (t * p + 1) % mod;
        res = res * t % mod;
    }
    cout << res << endl;

    return 0;
}

最大公约数

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int gcd(int a, int b){
    return b ? gcd(b, a % b):a;
}
int main()
{
    int n;
    cin >> n;
    while(n --){
        int a, b;
        cin >> a >> b;
        printf("%d\n", gcd(a,b));
    }

    return 0;
}