数论 - 因子

因数分解：

算术基本定理可以描述为：对于每个整数n，都可以唯一分解成素数的乘积

$n = p_1p_2p_3…p_k$

这里的素数并不要求是不一样的，所以可以将相同的素数进行合并，采用素数幂的乘积进行表示

$n = p_1^{e_1} p_2^{e_2} …p_k^{e_k}$

素数拆分：

（需要素数筛）：

int prime[MAX_1];
int visit[MAX_1];
int flag[MAX_1];
void Prime(int n)
{
    for(int i = 2;i <= n;i++)
    {
        if(!visit[i])
        {
            prime[++prime[0]] = i;//素数个数以及素数的值
            flag[i] = 1;//记录素数，可以改用map
        }
        for(int j = 1;j <= prime[0] && i*prime[j] <= n;j++)//素数筛精华
        {
            visit[i*prime[j]] = 1;
            if(i % prime[j] == 0) break;
        }
    }
}

因子：

map<int,int> cnt;
while(k != 1)//k为要求的数
{
	//prime 和 flag 均为素数筛提供
    for(int i = 1;i < prime[0];i++)
    {
        if(flag[k])//分解完成
        {
            cnt[k]++;
            k=1;
            break;
        }
        if(k % prime[i] == 0)
        {
            cnt[prime[i]]++;
            k /= prime[i];
            break;
        }
    }
}

因子个数：

$cntx = (e_1 + 1)(e_1+1)…(e_k+1)$

map<int,int>::iterator it;
int cntx = 1;
for(it = cnt.begin();it != cnt.end();it++)
{
    cntx *= (it->second + 1);
}

因子和：

map<int,int>::iterator it;
for(it = cnt.begin();it != cnt.end();it++)
{
    int k = 1;
    for(int i = 0;i <= it->second;i++)
    {
        k *= it->first;
    }
    ans *= (k-1) / (it->first -1);//包括本身和1
}