If Goldbach's conjecture is true, every positive integer, with a couple of trivial exceptions, can be expressed as a sum of either two or three primes. So, any string theory that replies on integers necessarily is not far removed from primes. And, since almost all numbers we use in math and physics can be related in precise ways to positive integers, all math is necessarily not terribly far removed from prime numbers.
Honestly, since a great deal of quantum physics generally, and string theory in particular, involves algebraic groups, whose most commonplace example is the math involved in modulo numbers (the Rubic's cube is a good physical representation of that kind of math), you probably need a set of numbers quite a bit less vast than the entire set of primes to solve all of its problems (although you probably need transcendental numbers like i and e and pi in addition to primes).
More generally, there is no good reason at all to think that non-prime numbers are necessary for strings to be unique without breaking up into composite states. Prime numbers are not additively fundamental (e.g. the number of quarks in a composite proton or neutron is three which is a prime number), and there is no a priori reason to think that just because you can imagine a particle or force associated with a particular number that such a particle or force actually exists. For example, there is no real profound quantum mechanical reason for there can't be fundamental spin 3/2 particles or spin 3 particles. If we found one we'd know just what to do, more or less. But, so far, the physicists putting together the Standard Model haven't found any experimentally (even indirectly), even though we have found (or probably found) fundamental particles of spins 0 (the Higgs boson), 1/2 (fermions) and 1 (Standard Model bosons), have a proposed particle of spin 2 (the graviton), and have composite particles of spin 3/2 (certain exotic baryons).
All string theories involve a hypothesis that all matter and energy and forces are manifestations of either one kind of string, or a combination of open strings and closed strings. The uniqueness and stability of these fundamentally identical strings that have different possible excitation states in different kinds of possible background space-times is an axiom of string theory rather than something that you prove with string theory. The trick is to recover something from those axioms that looks like the Standard Model and general relativity as a low energy approximation of the theory, and this turns out, however, to be profoundly non-unique, which is the basic problem that string theorists are stuck with these days.
