If this is easily 5Kyu, why is it marked as 6Kyu?

What you lack is confidence. You are 8Kyu. Try doing 20 8kyu numeric Katas, then 20 7kyu, then you'll be ready for this beast. I have to warn you that this Kata is easily a 5Kyu.See sentiments below.

You need a more efficient approach. For instance, for big numbers, you could only check from 1 to X, where X is a limit above which there would be no answer. The question now becomes "what is X?" Is it perhaps (n/2) + 1? Or is it something else?