I'm not sure if he originated the phrase, but Marcus du Sautoy, a professor of Mathematics at Oxford, used the phrase in his work "The Music of the Primes":

"It remains unresolved but, if true, the Riemann Hypothesis will go to the heart of what makes so much of mathematics tick: the prime numbers. These indivisible numbers are the atoms of arithmetic. Every number can be built by multiplying prime numbers together. The primes have fascinated generations of mathematicians and non-mathematicians alike, yet their properties remain deeply mysterious. Whoever proves or disproves the Riemann Hypothesis will discover the key to many of their secrets and this is why it ranks above Fermat as the theorem for whose proof mathematicians would trade their soul with Mephistopheles."

Atoms are tightly bound and hard to split, they are even harder to build. Up one level and starting with atoms the ease with which the next structures (molecules) can be created goes up tremendously (of course with a lot of variation depending on which atoms are used).

Prime numbers are can only be split (factorized) in one axiomatic way (1 and the prime itself). This is with multiplication(or it's inverse division) as the building (splitting) operation. Primes are tough to deal with, yet with them you can create (through multiplication) all other numbers. This is the fundamental theory of arithmetic.

The correlation is apparent. Though as explained with atoms we are creating structures that are made up of atoms but are not classified as atoms themselves (fusion can give you atoms from atoms but it is not easy business), but with primes numbers we make other numbers that are not primes.