从素数计算非素数因子

Question

有数字的，如510510

主因子是：[2, 3, 5, 7, 11, 13, 17]

使用素数列表，计算非素数因子的有效方法是什么？

Answer 1

假设素数因子列表包含根据重数的所有因子，您可以使用

prime_factors = [2, 3, 5, 7, 11, 13, 17]
non_prime_factors = [reduce(operator.mul, f)
                     for k in range(2, len(prime_factors) + 1)
                     for f in itertools.combinations(prime_factors, k)]

来得到所有的非素数因子。请注意，如果某些质数因子的重数大于1，则可能会得到重复项--可以使用set(non_prime_factors)过滤掉这些项。

(在这种情况下，NumPy不会有太多帮助。)

编辑:上面的“根据重数包含所有因子”我的意思是，如果2是重数为2的素数，那么它应该在列表中出现两次，即4是2的最高幂，这是该数的一个因子。

编辑2:如果有高重数的素数因子，上面的代码是低效的。因此，以防万一你需要这个，这里也有这个案例的有效代码。

primes = [2, 3, 5]
multiplicities = [3, 4, 5]
exponents = itertools.product(*(range(n + 1) for n in multiplicities))
factors = (itertools.izip(primes, e) for e in exponents if sum(e) >= 2)
non_prime_factors = [reduce(operator.mul, (p ** e for p, e in f))
                     for f in factors]

Answer 2

这里有一些可以让你开始的东西。在这种方法中，因子是它们在你的数字中出现的质数的映射。因此，对于您的情况，它看起来像[2 : 1, 3 : 1, 5 : 1, 7 : 1, 11 : 1, 13 : 1, 17 : 1]。注意，这会找到所有的除数，但修改应该是微不足道的。

def findAllD(factors):
    pCount = [0 for p in factors.keys()]
    pVals  = [p for p in factors.keys()]
    iters  = reduce(lambda x, y: x*y, [c+1 for c in factors.values()])
    ret    = []

    for i in xrange(0, iters):
        num = 1
        for j in range(0, len(pCount)):
            num *= pVals[j]**pCount[j]

        ret.append(num)

        for j in range(0, len(pCount)):
            pCount[j] = pCount[j] + 1

            if pCount[j] > factors[pVals[j]]:
                pCount[j] = 0
            else:
                break;

    return ret

Answer 3

由于数字510510等于2 *3*5*7* 11 * 13 * 17，因此每一对相乘的素数也是非素数：

>>> divmod(510510, 2*3)
(85085, 0)
>>> divmod(510510, 11*17)
(2730, 0)

6 (=2*3)和187 (=11*17)是非素数，并且是510510的propper因子。

您可以使用itertools轻松地找到所有数字对：

>>> a=[2, 3, 5, 7, 11, 13, 17]
>>> list(itertools.combinations(a, 2))
[(2, 3), (2, 5), (2, 7), (2, 11), (2, 13), (2, 17), (3, 5), (3, 7), (3, 11), (3,
 13), (3, 17), (5, 7), (5, 11), (5, 13), (5, 17), (7, 11), (7, 13), (7, 17), (11
, 13), (11, 17), (13, 17)]

然后，您需要做的就是将该对的第一个数字乘以第二个数字：

>>> a
[2, 3, 5, 7, 11, 13, 17]
>>> b=list(itertools.combinations(a, 2))
>>> [d*e for d,e in b]
[6, 10, 14, 22, 26, 34, 15, 21, 33, 39, 51, 35, 55, 65, 85, 77, 91, 119, 143, 187, 221]

最后，您需要对三元组、四元组等重复相同的过程，将合适的数字作为第二个参数传递给combinations()：

>>> b=[reduce((lambda o, p: o*p), y, 1) for x in xrange(2, len(a)) for y in itertools.combinations(a, x)]
>>> b
[6, 10, 14, 22, 26, 34, 15, 21, 33, 39, 51, 35, 55, 65, 85, 77, 91, 119, 143, 187, 221, 30, 42, 66, 78, 102, 70, 110, 130, 170, 154, 182, 238, 286, 374, 442, 105, 165, 195, 255, 231, 273, 357, 429, 561, 663, 385, 455, 595, 715, 935, 1105, 1001, 1309, 1547, 2431, 210, 330, 390, 510, 462, 546, 714, 858, 1122, 1326, 770, 910, 1190, 1430, 1870, 2210, 2002, 2618, 3094, 4862, 1155, 1365, 1785, 2145, 2805, 3315, 3003, 3927, 4641, 7293, 5005, 6545, 7735, 12155, 17017, 2310, 2730, 3570, 4290, 5610, 6630, 6006, 7854, 9282, 14586, 10010, 13090, 15470, 24310, 34034, 15015, 19635, 23205, 36465, 51051, 85085, 30030, 39270, 46410, 72930, 102102, 170170, 255255]