I was trying to solve this(LightOJ 1370) problem. When I failed to come up with a memory efficient solution, I looked at some AC solutions.

Interestingly, the solutions used a property that states that the minimum number that has a phi value greater than or equal to a given number, must be the first prime number greater than the given number. For example, For 20, the answer is 23. I am looking for a proof of this property.