python - Pyschools 质因数分解

Question

我正在做 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)   []              []

我该怎么做才能通过？

Answer 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]