Вычисление не простых делителей из простых чисел

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

чтобы получить все не простые факторы. Обратите внимание, что вы можете получить дубликаты, если некоторые простые факторы имеют большую кратность, чем один - их можно отфильтровать с помощью set(non_prime_factors).

(NumPy не слишком поможет в этом контексте.)

Редактировать: Под "содержит все факторы в соответствии с кратностью" выше, я имею в виду, что (скажем) 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]

Answer 2

Поскольку число 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]

Answer 3

Вот кое-что, с чего можно начать. В этом методе факторы составляют карту простых чисел с их вхождением в ваш номер. Итак, для вашего случая это будет выглядеть как [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 4

Если вы хотите создать ВСЕ делители 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).

Answer 5

Если D - это множество простых делителей N и d = |D|, чем N = \prod_i=1^d(D[i]^p[i]) для некоторых p[i] (где p [i] - натуральное число> 0).

С этой точки зрения вы можете использовать битовую маску, чтобы пройти через все возможные комбинации элементов из D и сгенерировать частичные произведения, которые разделят N. И, конечно, пройти все полномочия 1...p[i] для каждого элемента.

В этом случае вы получите все возможные не простые делители числа N.