Short "naive" question:
Is it true that faster algorithms require longer programs ?
Given a decision problem $A$ and a reasonable model of computation, there can be many ways (algorithms) to solve it, and some of them can be extremely inefficient or extremely efficient (when the time complexity of the algorithm matches the time complexity of the problem). For example the primality test can be done using the Sieve of Eratosthenes algorithm which is quite simple but requires exponential time or the AKS primality test which runs in polynomial time but is rather complex and requires a "lot of code".
Are there other examples of problems that can be solved "slowly" by a very simple algorithm, but the most efficient algorithm known is very complicated and requires a much bigger program?
What could be the underlying explanation for such behviour? (e.g. Kolmogorov complexity seems not to play any role)