我正在做 pyschools 练习,我在主题 5 问题 12 - 质因数分解上遇到问题,我必须这样做:
给定一个正整数,编写一个函数来计算可以相乘得到相同整数的质因数。
Examples
>>> primeFactorization(60)
[2, 2, 3, 5]
>>> primeFactorization(1050)
[2, 3, 5, 5, 7]
>>> primeFactorization(1)
[]
这是我的代码:
import operator
import functools as fun
def primeFactorization(num):
num = num
primes = []
result = []
if num > 1:
[primes.append(x) for x in range(2, num) if all(x % y != 0 for y in range(2, x))]
multy = fun.reduce(operator.mul, result, 1)
for number in primes:
if num % number == 0 and multy != num:
result.append(number)
return result
这会返回给我:
Test Cases Expected Result Returned Result
primeFactorization(33) [3, 11] [3, 11]
primeFactorization(84) [2, 2, 3, 7] [2, 3, 7]
primeFactorization(1) [] []
我已经尝试过这个,但私有(private)测试用例失败了:
import operator
import functools as fun
def primeFactorization(num):
num = num
primes = []
result = []
if num > 1:
[primes.append(x) for x in range(2, num) if all(x % y != 0 for y in range(2, x))]
multy = fun.reduce(operator.mul, result, 1)
for number in primes:
if num % number == 0:
result.append(number)
multy = fun.reduce(operator.mul, result, 1)
y = num/multy
if y != 1 and y in primes:
result.insert(0, int(y))
return result
Test Cases Expected Result Returned Result
primeFactorization(33) [3, 11] [3, 11]
primeFactorization(84) [2, 2, 3, 7] [2, 2, 3, 7]
Private Test Cases Passed Failed
primeFactorization(1) [] []
我该怎么做才能通过?
最佳答案
为什么要把事情搞得这么复杂?
查找给定数字 X
的所有质因数的问题与查找可整除 X
的最小数字(大于 1)的集合相同进入。
为了解决这个问题,我们可以从找到能整除 X
的最小数 n
开始。
这是X
的第一个素因数。然后我们可以通过查找 X/n
def primeFactorization(X):
possible = [2] + range(3,int(ceil(sqrt(X)))+1,2)
for p in possible:
if X % p == 0:
return [p] + primeFactorization(X/p)
return [X]
primeFactorization(3*3*7*5*11*13*31)
> [3,3,5,7,11,13,31]
关于python - Pyschools 质因数分解,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42853519/