Actually, prime numbers are pretty regularly distributed. So you can always find a prime number on a long enough segment. That's why yours and similar solutions work.