Для заданных пределов: 100_000 чисел, не превышающих миллион, работает самый простой алгоритм (1e10 вызывает distance()):
Для каждого числа в последовательности выведите его ближайшего соседа (как определеноминимальное расстояние):
solution = []
for i, ai in enumerate(numbers):
all_except_i = (aj for j, aj in enumerate(numbers) if j != i)
solution.append(min(all_except_i, key=lambda x: distance(x, ai)))
print(', '.join(map(str, solution)))
Где distance() можно рассчитать как (см. @ объяснение Влада ):
def distance(a, b):
"""
a = p1**n1 * p2**n2 * p3**n3 ...
b = p1**m1 * p2**m2 * p3**m3 ...
distance = |m1-n1| + |m2-n2| + |m3-n3| ...
"""
diff = Counter(prime_factors(b))
diff.subtract(prime_factors(a))
return sum(abs(d) for d in diff.values())
Где prime_factors() возвращает простые множителичисла с соответствующими кратностями {p1: n1, p2: n2, ...}:
uniq_primes_factors = dict(islice(prime_factors_gen(), max(numbers)))
def prime_factors(n):
return dict(multiplicities(n, uniq_primes_factors[n]))
Где multiplicities() функция задана n и ее множители возвращают их с соответствующими им кратностями (сколько раз множитель делит число без остатка):
def multiplicities(n, factors):
assert n > 0
for prime in factors:
alpha = 0 # multiplicity of `prime` in `n`
q, r = divmod(n, prime)
while r == 0: # `prime` is a factor of `n`
n = q
alpha += 1
q, r = divmod(n, prime)
yield prime, alpha
prime_factors_gen() дает простые множители для каждого натурального числа.Он использует алгоритм Sieve of Eratosthenes для поиска простых чисел.Реализация основана на gen_primes() функции @Eli Bendersky :
def prime_factors_gen():
"""Yield prime factors for each natural number."""
D = defaultdict(list) # nonprime -> prime factors of `nonprime`
D[1] = [] # `1` has no prime factors
for q in count(1): # Sieve of Eratosthenes algorithm
if q not in D: # `q` is a prime number
D[q + q] = [q]
yield q, [q]
else: # q is a composite
for p in D[q]: # `p` is a factor of `q`: `q == m*p`
# therefore `p` is a factor of `p + q == p + m*p` too
D[p + q].append(p)
yield q, D[q]
del D[q]
См. полный пример на Python .
Вывод
2, 1, 1, 2, 1, 2