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

すべての非素因数を取得します。一部の素因数の多重度が1より大きい場合、重複が発生する可能性があることに注意してください。これらは、を使用して除外できますset(non_prime_factors)。

（NumPyは、このコンテキストではあまり役に立ちません。）

編集：上記の「多重度に応じてすべての因子を含む」とは、多重度2の素因数である場合、（たとえば）2がリストに2回表示されることを意味します。つまり、4は2の因数である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)]

次に、ペアの最初の数を 2 番目の数に掛けるだけです。

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

最後に、トリプル、4 タプルなどに対して同じ手順を繰り返す必要があります。combinations() の 2 番目のパラメーターとして適切な数を渡します。

>>> 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|場合よりも大きい場合（p[i]は自然数>0）。N = \prod_i=1^d(D[i]^p[i])p[i]

この観点から、ビットマスクを使用して、からの要素のすべての可能な組み合わせを調べD、分割する部分積を生成できNます。1...p[i]そしてもちろん、各要素のすべての力を通過します。

この場合、Nのすべての可能な非素数除数を取得します。

于 2011-01-24T14:47:57.877 に答える
0

510510 のすべての約数を生成したい場合:

各素因数は、積に 1 回だけ表示されます。

各素因数は、使用することも使用しないこともできます。したがって、0 から 127 までのバイナリ セットと考えて、ビットを見てください。数値を反復処理し、素数の除数に関連するビットが設定されている場合は、その素数を含めます。

たとえば、バイナリ 1011010 は、数字 17、11、7、および 3 を使用することを意味するため、これらを乗算して 3927 を取得します。

もちろん、0000000 は 1 と 1111111 から 510510 に関連するので、「1 とそれ自体」を数えたくないかもしれません。

複数の因数を持つ数がある場合、その因数で 0 から n を数えなければなりません。たとえば、60 は 2 * 2 * 3 * 5 で、2 を 0-2 回使用し、3 を 0-1 回使用し、0-1 回を使用します。 5、全部で 12 の可能な因子 (1 と 60 を含む)。

于 2011-01-24T14:50:15.757 に答える