What's is the best strategy to use to solve this problem?

How many positive integers less than 72 have the property that the highest common factor of the number and 72.

I think I heard something about reducing 72 into its lowest prime numbers~ and then list the numbers less than 72 that do not have 2 or 3 as factors? But wouldn't that take a long time? Is there another efficient strategy?