This is tightly related to the *Jacobsthal function* defined to be the smallest integer $j(n)$ such that any segment of $j(n)$ consecutive integers contains an integer co-prime with $n$. Iwaniec proved that $j(n)=O(\log^2(n))$; this seems to imply your statement.