1

有一个数字，例如510510

主要除数是：[2, 3, 5, 7, 11, 13, 17]

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

4

5 回答 5

3

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

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

得到所有的非主要因素。请注意，如果某些主要因素的多重性大于一个，您可能会得到重复 - 这些可以使用过滤掉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]
于 2011-01-24T14:47:31.943 回答
1

这里有一些让你开始的东西。在这种方法中，因子是素数到它们在您的数字中出现的映射。因此，对于您的情况，它看起来像[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
于 2011-01-24T14:48:27.767 回答
1

由于数字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 的真除数。

您可以使用 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]

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

>>> 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]
于 2011-01-24T14:51:58.707 回答
0

如果 D 是 N 的素因数集合，则d = |D|对于N = \prod_i=1^d(D[i]^p[i])某些p[i]（其中 p[i] 是自然数 > 0）。

从这个角度来看，您可以使用位掩码来遍历元素的所有可能组合D并生成部分产品，这将划分N. 当然，还要通过1...p[i]每个元素的所有权力。

在这种情况下，您将获得 N 的所有可能的非素因数。

于 2011-01-24T14:47:57.877 回答
0

如果您的意思是要生成 510510 的所有除数：

每个主要除数在产品中只出现一次。

每个主要除数可以使用或不使用。所以把它想象成一个从 0 到 127 的二进制集并查看位。遍历这些数字，如果设置了与素数除数相关的位，则包括该素数。

例如二进制 1011010 表示使用数字 17、11、7 和 3，因此将它们相乘得到 3927

当然 0000000 与 1 相关，1111111 与 510510 相关，因此您可能不想计算“1 和它本身”。

如果您有一个具有多个因子的数字，则必须在该因子上计算 0 到 n，例如 60 是 2 * 2 * 3 * 5 所以 0-2 使用 2、0-1 使用 3、0-1 使用5、共有12个可能的因素（包括1和60）。

于 2011-01-24T14:50:15.757 回答