阶乘的素因式分解 [英] Prime factorization of a factorial

问题描述

我需要编写一个程序来输入数字并以以下形式输出其阶乘的素因式分解:

I need to write a program to input a number and output its factorial's prime factorization in the form:

4!=(2^3)*(3^1)

5!=(2^3)*(3^1)*(5^1)

问题是我仍然不知道如何获得该结果.

The problem is I still can't figure out how to get that result.

显然，括号中的每个第一个数字都是升序质数，直到实际阶乘为止.括号中的第二个数字是该数字在阶乘中出现的次数.

Apparently each first number in brackets is for the ascending prime numbers up until the actual factorial. The second number in brackets is the amount of times the number occurs in the factorial.

我不知道的是例如在5!=(2^3)*(3^1)*(5^1)中，如何在120(5！= 120)中仅发生3次2次，仅发生3次1次和仅发生5次.

What I can't figure out is for example in 5!=(2^3)*(3^1)*(5^1), how does 2 only occur 3 times, 3 only 1 time and 5 only one time in 120 (5!=120).

我现在已经解决了这个问题，这要归功于乐于助人的人士，但我现在很难设法找出一个数字并以这种格式获取阶乘，而无需实际计算阶乘.

I have now solved this thanks to the helpful people who commented but I'm now having trouble trying to figure out how could I take a number and get the factorial in this format without actually calculating the factorial.

推荐答案

每个数都可以由唯一的质数(最多重新排序)乘以质数表示，称为数的质分解.可以唯一创建该数字的主要因素.

Every number can be represented by a unique (up to re-ordering) multiplication of prime numbers, called the prime factorization of the number, as you are finding the prime factors that can uniquely create that number.

2^3=8

3^1=3

5^1=5

和8*3*5=120

但这也意味着:(2^3)*(3^1)*(5^1) = 120

并不是说数字120中的数字2代表3次出现，而数字2显然不是这样，而是2乘以2乘以2，总共为3的两倍.同样对于3和5，它们在120的素数分解中出现一次.您提到的表达式向您展示了数字120的唯一素数分解.这是在Python中获得数字的素数分解的一种方法: /p>

It's not saying that 2 occurs 3 times as a digit in the number 120, which it obviously does not, but rather to multiply 2 by 2 by 2, for a total of 3 twos. Likewise for the 3 and 5, which occur once in the prime factorization of 120. The expression which you mention is showing you this unique prime factorization of the number 120. This is one way of getting the prime factorization of a number in 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，如上所述.这是一个小图，可以更清楚地说明这一点:

Which multiplied together give you 120, as explained above. Here's a little diagram to illustrate this more clearly:

这篇关于阶乘的素因式分解的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！