如何找到并打印一个正整数的质因数分解?

Question

""""
A function that takes a positive integer n as input and prints its prime factorization to 
the screen. 
Gather the factors together into a single string, so that the results of a call like
(60) would be to print the string “60 = 2 x 2 x 3 x 5” to the screen.
Looking for a way to build prime_factorization such that every factor you find will be prime 
automatically.
"""
def prime_factorization(n):
results = 0
for i in range(1, n + 1):
if (n % i) == 0:
prime = True
for x in range(2, i):
if (i % x) == 0:
prime = False
if prime:
results = results + i
return results
prime_factorization(60)

以上就是我对这个问题的尝试。我试着先找出因子，然后确定它们是否为质数。我非常坚持这一点，并将感谢任何帮助或建议!

Answer 1

尝试编写这个算法。不需要对素数进行测试，但对于素数因子非常大的数不有效。

1. 让f = 2
2. 计算f成n的商和余数
3. 如果没有余数，保存f，让n =商
4. 如果剩余，增加f
5. 重复2-4，直到n == 1。
6. 返回保存的因子。

计算1-10,000的质因数花了~2秒，但计算下一个10,001到20,000花了~5.5秒。从那以后情况会变得更糟，但之后你会寻求优化。