# Minimum set of US coins to count each prime number less than 100

Say I wanted to be able to carry enough coins in my pocket such that at any time, I could count out exact change totaling any of the prime numbers less than 100. How would I determine the minimum set of coins I would need to carry? I don't care about being able to count out multiple primes - meaning the set does not have to remain useful after one number has been counted out.

So, given the standard US coins: penny, nickel, dime, and quarter - what would be the minimum number of each coin that I would need to be able to count out exactly 3, 5, 7, 11 up to 97 cents.

-
Are you asking for the minimum for each prime separately, or are you asking for the minimum collection that suffices to make every prime amount less than $100$? –  Brian M. Scott May 10 '12 at 3:17

If you want one set of coins that can add to all primes, you need 4 pennies so you can do 19. You also need a nickel for 19. Two nickels are dominated by dime+nickel, so you only want one. You clearly want three quarters to get close to 97. As three quarters, one dime, one nickel, and four pennies can't do 97 you need two dimes. So: three quarters, two dimes, one nickel, and four pennies makes ten coins.

-