As for the construction, any equivalence relation on a set defines a partition of the set.
So if you can define an equivalence relation on with a denumerable collection of infinite equivalence classes that will also do for your set.
Here is a suggestion.
Two positive integers are related if they are powers of the same prime or neither is a power of a prime.
Can you prove that is an equivalence relation?