A rainbow list would be impractically large and a nightmare to build in terms of cpu cycles. If you look up distribution of primes you can get a reasonable approximation to the number of primes in any range and we are talking 10^100 ish. (Yes, I haven't checked my number theory book for a few years). The bigger the prime the more it costs per prime to find it - see other Vulture articles. Unless we get serious quantum computing.
Why use primes? - because they are what give unique decription, hairy group and number theory from what little I remember and you probably have to check the specific algorithm to see why.