在Python中分解数字 [英] Factorizing a number in Python

问题描述

这是我的代码:

def factorize(n):
    sieve = [True] * (n + 1)

    for x in range(2, int(len(sieve) ** 0.5) + 1):
        if sieve[x]: 
            for i in range(x + x, len(sieve), x):
                sieve[i] = False

lowerPrimes = i for i in range(2, len(sieve)) if sieve[i]] and (n % i == 0)]
return lowerPrimes

factorize(n)返回给定值n的所有素数.如您所见，它首先为n制作一个Eratosthenes筛，然后使用列表推导返回该筛中作为n因子的所有值.为此，它工作得比较好，但是，我希望它返回一个列表，这样，如果将其中的每个项目相乘，结果就是n.你明白我的意思吗?

factorize(n) returns all prime factors of the given value n. As you can see, it first makes an Eratosthenes sieve for n and then uses a list comprehension to return all values in the sieve that are factors of n. It works relatively fine for this purpose, however, I want it to return a list so that if you multiply every item in it, the result is n. Do you get my point?

例如，factorize(99020)返回[2, 5, 4951]，但是我希望它以2*2*5*4951 = 99020的形式返回[2, 2, 5, 4951].

For example, factorize(99020) returns [2, 5, 4951], but I'd like it to return [2, 2, 5, 4951], as 2*2*5*4951 = 99020.

我知道我的方法还差得远，但是你能帮我做到吗?

I know my approach is not even close, but could you help me to make it so?

推荐答案

Eratosthenes筛网可帮助您找到低于特定限制的质数.并不能真正帮助您找到特定数字的因数.

The Sieve of Eratosthenes helps you find prime numbers below a certain limit. It's not really going to help you with finding the factors of a particular number.

如果您想这样做，我可以看到的最简单的方法是这样的:

If you want to do that, the simplest approach that I can see is something like this:

def factors(n):
    while n > 1:
        for i in range(2, n + 1):
            if n % i == 0:
                n /= i
                yield i
                break

for factor in factors(360):
    print factor

这基本上找到了n的最小因子(保证是质数)，将n除以该数字，然后重复该过程，直到n等于1.

This basically finds the smallest factor of n (which is guaranteed to be prime), divides n by that number and repeats the process until n is equal to 1.

输出为:

2
2
2
3
3
5

它们相乘成原始数字:

>>> from operator import mul
>>> reduce(mul, factors(360))
360

这篇关于在Python中分解数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！