Brainteaser 1721: Prime leaps

From The Sunday Times, 10th September 1995 [link]

The history-cum-maths teacher asked the class to name some years which the knew from history lessons. Johnny named 1066, the Battle of Hastings, and 1939, the outbreak of the Second World War. The teacher then asked him to calculate the difference between the two and Johnny got the correct answer of 873.

The teacher then asked Johnny if this difference was prime and Johnny answered correctly that it was not because, for example, it was divisible by three.

The teacher then asked the class to find the longest list of years they could from 0, 1, 2, …, 1999, 2000 so that for any two numbers in the list their difference was not prime.

Which numbers are in the longest such list?

This puzzle was included in the book Brainteasers (2002, edited by Victor Bryant). The puzzle text above is taken from the book.

[teaser1721]