If N is the product of all prime numbers less than k, then the numbers N+2,N+3,...,N+k are all composite. This is the best upper bound that I can find without doing a brute force search. I wrote a Maple program to search for the first prime gap of 100 or more. I am not a programmer, so please don't laugh too hard: for i from 100 to 1500000 by 100 while nextprime(i) - prevprime(i) < 100 do od; The result is that there are no prime numbers between 370261 and 370373.