Now I see where the problem was… and probably all people there who can not solve this have the same problem…
Sometimes even a good meant advise (hint) can confuse people if it is understood literally and people do not think about what it really could mean
Someone here said that primes are not too far from each other… so people start to think that difference of p-q (or p-sqrt(n)) is small, but that is not the case, in fact the distance of primes is quite big.
So if your method was to check every prime above Floor(sqrt(n))+1 whether it divides n then it can take billions of years (my guess) to find the answer…
What was meant by the hint is that primes are near each other enough that it is easy to find them with some efficient method… in this case Fermat's factorization method
So just apply simple Fermat's factorization method and the result is guaranteed