Целочисленное расстояние

Под единственной операцией между двумя положительными целыми числами мы понимаем умножение одного из числа на некоторое простое число или деление его на (при условии, что оно может быть разделено на это простое число без остатка). Расстояние между a и b обозначается как d (a, b ) - это минимальное количество операций, необходимых для преобразования числа a в число b. Например, d (69,42) = 3.

Имейте в виду, что наша функция d действительно имеет характеристики расстояния - для любых положительных чисел a, b и c получаем:

a) d (a, a) == 0

b) d (a , b) == d (b, a)

c) неравенство треугольника d (a, b) + d (b, c)> = d (a, c) является fu lfilled.

Вам будет дана последовательность положительных целых чисел a_1, a_2, ..., a_n. Для каждого a_i из них выведите такой a_j (j! = I), чтобы d (a_i, a_j) было как можно меньше.Например, последовательность длины 6: {1,2,3,4,5,6} должна выводить {2,1,1,2,1,2}.

Мне это кажется действительно трудным. Я думаю, что было бы полезно:

a) если a_i простое число, мы не можем сделать ничего меньше, чем a_i (если оно не равно 1), поэтому единственная разрешенная операция - это умножение. Следовательно, если у нас есть 1 в нашем наборе, для каждого простого числа d (this_number, 1) будет наименьшим.

b) также для 1 d (1, any_prime_number) является самым низким.

c) для непростого числа мы проверяем, есть ли у нас какие-либо его множители в нашем наборе, или умножение его множителей

Это все, что я могу вывести. Хуже всего то, что я знаю, что потребуется вечность, чтобы такой алгоритм работал и проверял все возможности ... Не могли бы вы помочь мне с этим? Как это сделать?