[Python] How'd you make algorithm that'll find shortest way to sort sequence of numbers just...

Imagine you get sequence of integers:

[a1 a2 a3 ... an]


where:

1 <= a <= 10^6
1 <= n <= 10^6


You are given a function f(x) that can change a number to the closest lower prime number, or to 1 if there is no lower prime.

I need an algorithm that finds the shortest use of f(x) trying to sort the sequence, either in descending or ascending order.

I tried writing a program in Python that would first make a sequence of all prime numbers up to the highest number using the Sieve of Eratosthenes algorithm, and then loops through the numbers, lowering them accordingly. I'd try descending and ascending and then pick the lower number of operations. However, it was too slow.

Continue reading...