Imagine that you have a collection of very weird dice. For every prime between 1 and 1000, you have a fair die with that many sides. Your goal is to generate a uniform random integer from 1 to 1001 inclusive.
For example, using only the 2 sided die, you can roll it 10 times to get a number from 1 to 1024. If this result is less than or equal to 1001, take that as your result. Otherwise, start over.
This algorithm uses on average 10240/1001=10.228770… rolls. What is the fewest expected number of die rolls needed to complete this task?
When you know the right answer, you will probably be able to prove it. This puzzle is my own design. Solution in the comments.