Hoheisel's theorem states that there is some $\delta> 0$ and some $x_0>0$ such that for all $x > x_0$ the interval $[x,x+x^{1-\delta}]$ contains prime numbers. Classically this is proved using the Riemann zeta function and results about its zeros such as the zero-free region and zero density estimates. In this talk I will describe a new elementary proof of Hoheisel's theorem. This is joint work with Kaisa Matomäki (Turku) and Joni Teräväinen (Cambridge). Instead of the zeta function, our approach is based on sieve methods and ideas coming from additive combinatorics, in particular, the transference principle. The method also gives an L-function free proof of Linnik's theorem on the least prime in arithmetic progressions.