主要因素编辑

Question

我有这个代码

def primefactor(n):
    d = 2
    factors = [ ]
    while n > 1:
      if n % d == 0:
        primefactors.append(d)
        n = n//d
      else:
          primefactors.append(d)
    return factors

print(factor1(20))
[2, 2, 5]

每次我删除一行，什么都不打印出来。即使有些东西应该。有没有更有效的方法在不使用任何库的情况下获取数字的所有质因数？？。

Answer 1

这是一个使用 lambda 和 map

计算素数的有趣方法

limit = 100
primelist = lambda n : [x for x in range(2, n) if not 0 in map(lambda z : x % z, range(2,x))]
print ", ".join(map(str, primelist(limit)))

Answer 2

此解决方案同时使用了您的原始想法和@user1767754

的post

def factor1(n):
    primelist = lambda n: [x for x in xrange(2, n) if not 0 in map(lambda z : x % z, xrange(2,x))]
    factors = [ ]
    for d in primelist(n):
        if n % d == 0:
            factors.append(d)
    return factors

该程序使用 primelist 函数生成所有质数，直到它正在寻找质因数的数字 n。对于这些数字中的每一个，它都会像以前一样检查可除性，并将素数附加到 factors 列表中。

至于你的原始代码，正如@alfasin 在评论中所说，你的程序在大多数情况下进入无限循环，它也不会检查所有素数，并将潜在的非素数添加到结果。

一个更简单但不优雅的解决素数查找问题的方法是例如如下附加功能：

def get_primes(n):
    primelist = []
    for d1 in range(2,n):
        flag = 0
        for d2 in range(2,d1):
            if d1 % d2 is 0:
                flag = 1
                break
        if flag is 0:
            primelist.append(d1)
    return primelist

此处与在 lambda 中一样，程序检查每个数字的可整性，直到目标数字 n 所有数字都小于当前数字。该标志用于表示当前处理的数字是否被发现可以被任何东西整除（除了 1 和它本身）。如果标志为 1，则该标志被赋予值 1，并为每个新数字重置。结果与 lambda 完全相同 - 直到目标数的素数列表，可以按如下方式使用，

def factor1(n):
    factors = [ ]
    primelist = get_primes(n)
    for d in primelist:
        if n % d == 0:
            factors.append(d)
    return factors

以后请记住，嵌套循环解决方案并不理想，应该用列表理解、lambda、映射等代替。

Answer 3

试试这个，

def primefactors(N):
    factors = []
    i = 2
    while i <= N:
        while N % i == 0:
            factors.append(i)
            N = N/i
        i += 1
    return factors

但请记住，此方法将执行 N 步，因此时间效率与输入大小成指数关系。

Answer 4

下面是一个计算质因数的简单程序：

$ python
Python 2.7.13 (default, Mar 13 2017, 20:56:15)
[GCC 5.4.0] on cygwin
Type "help", "copyright", "credits" or "license" for more information.
>>> def factors(n):
...     f, fs = 2, []
...     while f*f <= n:
...         if n % f == 0:
...             fs.append(f)
...             n /= f
...         else:
...             f += 1
...     fs.append(n)
...     return fs
...
>>> factors(20)
[2, 2, 5]

如果 n 很大，有更好的方法求它的因子：google for "Pollard rho", "elliptic curve factorization", or "quadratic sieve".

主要因素编辑

Prime factors edit

python

prime-factoring