Любое целое число может быть представлено как произведение степеней простых чисел:
I = 2^p1 * 3^p2 * 5^p3 * 7^p4 * 11^p5 * ....
Общее количество всех его факторов равно
N = (p1+1) * (p2+1) * (p3+1) * ....
\__________________________/
K multipliers
Таким образом, вам нужно представить значение N
как произведение K
факторов больше 1.
Разложить N на простые числа, сгруппировать эти простые числа в K групп.
Представьте, что у вас есть N=420
с 5 простыми факторами: 2 2 3 5 7
и K=3
. Создайте группы 2*2, 3*5, 7
(или любую другую комбинацию), чтобы соответствующие полномочия I
составляли 3,14,6
Например, имея N = 12
и K=3
, вы можете представлять 12 = 2 * 2 * 3
и использовать произведение любых двух простых чисел с квадратом третьего простого числа как число I
. Наименьшее такое значение - 60 (2^2 * 3 * 5)
, следующее - 90 (2 * 3^2 * 5)
и т. Д. (Например, 3 * 7 * 11^2
также является решением).
Для случаев N = 12
и K=2
вы можете представляют 12 = 3 * 4
и получают результаты в виде p^2*q^3
или 12 = 2 * 6
и получают результаты в виде p*q^5
, где p,q
являются различными простыми числами
Для случая N = 12
и K=4
вы не можете представить 12
как произведение четырех целых чисел больше 1
, поэтому невозможно получить результат с этими аргументами