The intuition that the difficulty of factoring comes from the mysteries surround prime numbers is compelling, but it is also somewhat muddied by other known results. For example, a famous result [1] showed that testing whether a given number is prime, actually CAN be done in efficiently (i.e., in polynomial time), unlike integer factorization (that we know of).
Some discussion of why some believe factoring could be easy can be found here: [2]