Frequency is continuous, so it doesn't make sense to talk about "primes" here at all - prime number theory belongs to the realm of integers.
Two frequencies harmonize (per Archimedes) when they are in a ratio that can be described as a "simple" rational number (i.e. the numerator and denominator are small when reduced to lowest terms). Practically speaking, it tends not to bother us much if things are very slightly off - although sometimes one can hear "beat frequencies" as a result.
Instruments used to be tuned to emphasize harmony based on certain keys. For example, the G on a piano might be tuned to exactly 1.5 times* the frequency of the C below it (correspondingly, .75 times the frequency of the C above it, as an octave always represents an exact doubling in frequency). This would make pieces written in C major sound perfectly "harmonious", and others nearly so, at the expense of other keys being rather muddled in sound. Historical associations of keys to "types" of music (e.g. military marches, and Chopin's
Polonaise No. 1, being in D major and/or A major) are largely based on the character of the sound that resulted from the historical tuning.
In the modern era, instruments are "well-tempered", meaning that the frequency ratio between any two adjacent semitones is the same: the 12th root of two (or at least, as near as the tuner can get it). Thus every key sounds equally good (at least in theory), and you can transpose things freely (typically, in order to best suit the instruments and/or vocalists that will be performing the arrangement).
See also. ("Traditional" selection of keys for pieces evidently continued for a long time after the development of the "well-tempered clavier", and may even be consciously thought about today.)
Of course, electronic music holds itself free to throw all of that out the window, and other world cultures have differently divided scales. It's very difficult to train yourself to sing with a new scale-division once you can use one of them well, BTW. :) It seems that one develops a very strong "muscle memory" in the vocal cords.
* Note that
there are 7 semitones between C and G.