1、质数

（1）质数判断：试除法 O( sqrt(n) )

#include<iostream>

using namespace std;

int prime(int n)
{
    if (n < 2)
        return 0;

    for (int i = 2; i <= n / i; i++)
        if (n % i == 0)
            return 0;

    return 1;
}

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

    if (prime(n))
        cout << "是素数" << endl;
    else
        cout << "不是素数" << endl;

    return 0;
}

（2）分解质因子:输出质因子底数和质数 O( sqrt(n) )

#include<iostream>

using namespace std;

void divide(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (n % i == 0)
        {
            int s = 0; //s是指数，i是质因子底数
            while (n % i == 0)
            {
                n /= i;
                s++;
            }

            cout << i << " " << s << endl;
        }
    }

    if (n > 1)
        cout << n << " " << "1" << endl;  //n是自身的质因子
}

int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        int x;
        cin >> x;
        divide(x);
    }

    return 0;
}

（3）筛质数 ：线性筛法

#include<iostream>

using namespace std;
const int N = 100010;
int primes[N], cnt;  //存质数, 质数个数
bool st[N];  //true表示是质数

void getprimes(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (st[i] == false)
            primes[cnt++] = i;

        for (int j = 0; primes[j] <= n / i; j++)
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0)  //prime[j]一定是i的最小质因子
                break;
        }
    }
}

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

    getprimes(n);

    cout << cnt << endl;

    return 0;
}

二、约数

（1）求一个数的所有约数：试除法

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

vector<int> divisors(int n)
{
    vector<int> ans;
    for (int i = 1; i <= n / i; i++)
    {
        if (n % i == 0)
        {
            ans.push_back(i);
            if (i != n / i)  //平方只存一个
                ans.push_back(n / i);
        }
    }

    sort(ans.begin(), ans.end());  //从小到大排序
    return ans;
}

int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        int x;
        cin >> x;
        vector<int> ans = divisors(x);

        for (int i = 0; i < ans.size(); i++)
            cout << ans[i] << " ";
        cout << endl;
    }

    return 0;
}

约数个数和约数之和看云记笔记

（4）最大公约数：欧几里得算法（辗转相除法）

#include <iostream>

using namespace std;

int gcd(int a, int b)
{
    if (b != 0)
        return gcd(b, a % b);  //a和b的最大公约数 == b和（a % b）的最大公约数
    else
        return a;
}

int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        int a, b;
        cin >> a >> b;
        cout << gcd(a, b) << endl;
    }

    return 0;
}

三、欧拉函数

(1)定义求法 O(nlogn)

#include<iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        int a;
        cin >> a;

        int res = a;
        for (int i = 2; i <= a / i; i++)
            if (a % i == 0)
            {
                res = res / i * (i - 1);
                while (a % i == 0)
                    a /= i;
            }

        if (a > 1)
            res = res / a * (a - 1);

        cout << res << endl;
    }

    return 0;
}