представление числа как умножение его факторов

Question

Я хочу представить число как произведение его факторов. Количество факторов, которые используются для представления числа, должно быть от 2 до числа простых коэффициентов одного и того же числа (это максимально возможное число факторов для числа).

, например, принимая число 24:

представления числа, как два фактора умножения являются 2*12, 8*3, 6*4 и так далее ...

представления числа, как три фактора умножение 2*2*6 , 2*3*4 и т. Д.,

Представление числа как умножение четырех факторов (только простые множители) - 2*2*2*3.

пожалуйста, помогите мне получить простой и общий алгоритм для этого

Answer 1

Я знаю один ...

Если вы используете Python, вы можете использовать словарь для упрощения хранения ...

Вам нужно будет проверить каждый штрих меньше квадратного корня из числа.

Теперь предположим, что p^k делит ваше число n, ваша задача, я полагаю, это найти k. Вот что:

int c = 0; int temp = n; while (temp! = 0) {temp/= p; c + = temp; }

Выше код C++, но вы получите идею ... В конце этого цикла вы будете иметь с = K

И да, ссылка дается воли идеальная реализация на питоне того же алгоритма

Answer 2

Вот функция, которая возвращает все факторы заданного числа, n. Обратите внимание, что он возвращает каждый отдельный фактор, а не определенную пару.

def factors(n): 
    """Finds all the factors of 'n'""" 
    fList, num, y, limit = [], n, 0, int(sqrt(n)) + 1 
    for factor in range(1, limit): 
     if n % factor == 0: 
      if factor not in fList: fList.append(factor) 
      y = n/factor 
      if y not in fList: fList.append(y) 
    return sorted(fList) 

Например, :

>>> factors(24) 
[1, 2, 3, 4, 6, 8, 12, 24] 

Answer 3

Это произведет все множества факторов, которые размножаются, чтобы дать исходное число. Он возвращает все наборы продуктов как уникальный список отсортированных кортежей.

1 s исключены, чтобы избежать бесконечной рекурсии.

def prime_factors(n):  
    return set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))) 

def product_sets(n): 
    return set(products(1, [], n, prime_factors(n))) 



def products(current_product, current_list, aim, factors): 

    if current_product == aim: 
     yield tuple(sorted(current_list)) 

    elif 0 < current_product < aim: 
     for factor in factors: 
      if factor != 1: 
       for product in products(current_product * factor, current_list + [factor], aim, factors): 
        yield product 


print list(product_sets(24)) 

Выход:

[(4, 6), (3, 8), (2, 12), (2, 3, 4), (24,), (2, 2, 6), (2, 2, 2, 3)]