Exactly 150 primes

[karthickgururaj]

Show that there is a set of 2002 consecutive positive integers containing exactly 150 primes. (You may use the fact that there are
168 primes less than 1000)

 

(original source: from a training set for IMO).

[witzar]

Let P(n) denote the number of primes in set {n, n+1, ..., n+2001}

(the set of 2002 consecutive positive integers starting with n).
We are given that P(1)>=168.
First observe that P(2003!+2) = 0. Indeed k | (2003!+k) for k=2, 3, ..., 2003,
so each number in set {2003!+2, 2003!+3, ..., 2003!+2003} is composite.
Now observe that |P(n+1) - P(n)| <= 1. Indeed, shifting the set by one to the right
cannot change the number of primes in the set more then by 1.
Therefore P(n) takes all intermediate values between P(1)(>=168) and P(2003!+2) (=0),
so the value of 150 is also taken for some 1<n<(2003!+2) in particular.