一、数论

1.分解质因数

int n; //需要分解的数
int cnt; // 计数器
int p[100005]; // 底数
int a[100005]; //指数
for (int i = 2;i * i <= n;i++)
{
    if (n % i == 0)
    {
        p[cnt] = i;
        while (n % i == 0)
        {
            n /= i;
            a[cnt]++;
        }
        cnt++;
    }
    if (n > 1)
    {
        p[cnt] = n;
        a[cnt] = 1;
        cnt++;
    }
}
/*** p存储底数
     a存储指数
     cnt为因数个数 - 1
*/

2.因数个数和因数和

// 需先分解质因数
int c = 1,s = 1;// c为个数，s为因数之和
for (int i = 0;i < cnt;i++)
{
    c *= a[i] + 1;
    int t = 1;
    for (int j = 0 ;j <= a[i];j++)
    {
        c += t;
        t *= p[i];
    }
    s *= t;
}

3.最大公因数

（1）直接调用gcd函数

gcd = __gcd(a,b);

（2）

int gcd (int a,int b)
{
    if (b == 0)  return a;
    return (b,a % b);
}

4.埃氏筛法

bool vis[1000005];// vis[i] == 1是质数，否则不是质数
bool prime()
{
    for (int i = 1;i <= 1000000;i++)  vis[i] = 1;
    vis[0] = vis[1] = 0;
    for (int i = 2;i <= 1000000;i++)
    {
        if (vis[i] == 1)
        {
            for (int j = i * 2;j <= 1000000;j+=i)
            {
                vis[j] = 0;
            }
        }
    }
}

5.质因子分解

唯一分解定理：给定一个大于1的正整数n，一定可以写成：n = p1^a1 * p2^a2 * ……pn*ai;

p1,p2……pn都是质数。

int n;
cin >> n;
for (int i = 2;i * i <= n;i++)
{
    while(n % i == 0)
    {  
        cout << i << " ";
        n /= i;
    }
}
if (n != 1)
    cout << n;