阶乘分解质因数

对  $n!$  进行质因子分解。

input

12

output

2 10
3 5
5 2
7 1
11 1

思路

首先知道一个简单数怎样分解质因数： 遇到一个质因子时便将其除尽

for(int i = 2; i <= x / i; i++)
{
	if(x % i == 0)
	{
		int cnt = 0;
		while(x % i == 0)
		{
			x/=i;
			cnt++;
		}
		cout << i << "^" << cnt;
	}
}

对于阶乘这个大整数不能通过算出阶乘然后分解质因数来解。 那就只能枚举$1-n$中所有质数 p, 并求出对应的指数 k 对于$n!$的质因子 p 的指数 我们来一个样例说明一下：

1  2  3  4  5  6  7  8         我们求得在 8！中 2 的个数

1      1      1      1         首先我们先计算出 2 的倍数的个数：8/2=4

1              1         其次我们计算出 4 的倍数的个数：    8/4=2（上面一个式子求出了第一层，现在求第二层）

1         最后我们解出第三层的 2 的个数：    8/8=1

我们把 4+2+1=7，所以一共 7 个 2 出现了。

即：$cnt(x)=[\frac{n}{(x^1)}]+[\frac{n}{(x^2)}]+[\frac{n}{(x^3)}]+...(直到x的次方大于n)$

到这里我们可以发现：我们平时求的方法是一列一列求的（就是每一个数算一遍），而这个方法我们每一行每一行的求，虽然效果一样，但求起来速度很快。值得学习。

故做法：

1.先把素数表打好

2.for 循环把小于 n 的每个质数进行一次运算，用数组记录

3.结束

非常快。

int main()
{
    int n;
    cin >> n;
    for (int i = 2; i <= n; i++)
    {
        bool isprime = true;
        for (int j = 2; j <= i / j; j++)
            if (i % j == 0)
            {
                isprime = false;
                break;
            }
        if (isprime)
        {
            int cnt = 0;
            for (int k = i; k <= n; k *= i)
                cnt += n / k;
            cout << i << " " << cnt << endl;
        }
    }
    return 0;
}