  Let $G(X)$ denote the size of the largest gap between consecutive primes
below $X$. Answering a question of Erdos, we show that $$G(X) \geq f(X)
\frac{\log X \log \log X \log \log \log \log X}{(\log \log \log X)^2},$$ where
$f(X)$ is a function tending to infinity with $X$. Our proof combines existing
arguments with a random construction covering a set of primes by arithmetic
progressions. As such, we rely on recent work on the existence and distribution
of long arithmetic progressions consisting entirely of primes.
