我需要编写一个程序，输入一个数字并输出它的阶乘的质因数分解结果，格式如下：
4!=(2^3)*(3^1)
5!=(2^3)*(3^1)*(5^1)
5!=(2^3)*(3^1)*(5^1)中，如何只使2出现3次，3只出现1次，5只出现1次。每个数字都可以用质数的唯一（顺序可变）乘积表示，称为该数字的质因数分解，你正在寻找能唯一创建该数字的质因数。
2^3=8
3^1=3
5^1=5
而8*3*5=120
但这也意味着：(2^3)*(3^1)*(5^1) = 120
它并不是说数字120中有3个2，显然并没有，而是将2乘以2再乘以2，共计3个2。对于3和5也是如此，它们在数字120的质因数分解中只出现一次。你提到的表达式向你展示了该数字的唯一质因数分解。这是在Python中获取数字质因数分解的一种方式：
def pf(number):
factors=[]
d=2
while(number>1):
while(number%d==0):
factors.append(d)
number=number/d
d+=1
return factors
运行它，您将得到：
>>> pf(120)
[2, 2, 2, 3, 5]
如上所述，它们相乘可以得到120。以下是一个简单的图示：
考虑例如 33!。 它是以下数值的积：
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
这些因素包括：
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2
2 2 2 2
2 2
2
3 3 3 3 3 3 3 3 3 3 3
3 3 3
3
5 5 5 5 5 5
5
7 7 7 7
11 11 11
13 13
17
19
23
29 31
你看到这个模式了吗？
33! = 2^( 33 div 2 + 33 div 4 + 33 div 8 + 33 div 16 + 33 div 32) *
3^( 33 div 3 + 33 div 9 + 33 div 27) *
5^( 33 div 5 + 33 div 25) *
----
7^( 33 div 7) * 11^( 33 div 11) * 13^( 33 div 13) *
----
17 * 19 * 23 * 29 * 31
n!的质因数分解，而不进行任何乘法或因式分解，我们只需要有不大于n的素数的有序列表，我们将其分为三个阶段处理（通过重复整数除法和可能的求和）-小于等于n平方根的质数，小于等于n/2的质数以及剩余的质数。
实际上，使用惰性求值甚至比这更简单。假设primes在Haskell中已经实现并返回按顺序排列的质数流，阶乘分解可以找到：
ff n = [(p, sum . takeWhile (> 0) . tail . iterate (`div` p) $ n)
| p <- takeWhile (<= n) primes]
-- Prelude> ff 33
-- [(2,31),(3,15),(5,7),(7,4),(11,3),(13,2),(17,1),(19,1),(23,1),(29,1),(31,1)]
因为33 div 4等于(33 div 2) div 2，以此类推。
2^3是另一种写法，意思是2的3次方。(2^3)(3^1)(5^1)= 2的3次方 × 3 × 5 = 120，这就是120的质因数分解式用普通ASCII文本表达而不是数学格式化。之所以要求输出的格式如此简单，只是为了让您更容易地输出，而不是为了让您弄懂如何输出格式化的等式（还可能更容易得到评分）。在此处使用的文本表示方程的约定是标准的，您可以直接将此文本输入google.com或wolframalpha.com中，它将为您计算结果为120: 在wolframalpha.com上的(2^3)(3^1)(5^1) / 在google.com上的(2^3)(3^1)(5^1)
ab × ac = ab+c
10 × 15 = (21 × 51) × (31 × 51) = 21 × 31 × (51 × 51) = 21 × 31 × 52 通过上面的计算，我们可以看出，计算10×15的质因数分解并不需要将10乘以15；相反，你可以先计算每个数字的质因数分解，然后再将这些分解组合起来。公式（a） 10 = 21 × 5 1
公式（b） 15 = 31 × 51
10 × 15 = ? 使用公式（a）和公式（b）的右侧来回答，而不使用数字150。
O(n/2 log log n) 算法。f = a * b ~> f^k = a^k * b^k
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char **argv) {
int n = atoi(argv[1]);
int *p = (int *) malloc(sizeof(int) * (n + 1));
int i, j, d;
for(i = 0; i <= n; i++)
p[i] = 1;
for(i = n >> 1; i > 1; i--)
if(p[i]) {
for(j = i + i, d = 2; j <= n; j += i, d++) {
if(p[j]) {
p[i] += p[j];
p[d] += p[j];
p[j] = 0;
}
}
}
printf("1");
for(i = 2; i <= n; i++)
if(p[i])
printf(" * %i^%i", i, p[i]);
printf("\n");
return 0;
}
N，输出将包含太多条目 - 约为N /（log N-1） 条目（与N以下的质数一样多）。 对于10^9，它有50,701,542个条目（实际上是50,847,534）。 我想我们不需要做那么多。 :) 因此，我认为任何正常的SoE实现都可以，无论是预先计算还是作为算法的一部分。 :) - Will Ness
2*2*2 * 3 * 5等于120，对吧？你对此有什么困惑吗？ - Keith Thompson