More generally it's one of the problems faced by the intuitionist mathematician - if all mathematics is a human construct/invention/logic game, then how come it keeps turning out to be so incredibly useful in unlooked for real world applications?

I think the amazing thing about prime numbers is that they are so fundamental and basic and yet so strangely and unpredictably behaved.