There are so may Pokemon that learn moves on primes, I decided to list the ones that DON'T learn moves son primes.
Gen 1 ( I included A-Forms because they are very similar to the regular ones, and they are all Gen 1).
Caterpie, Metapod, Weedle, Kakuna, Wigglytuf, Clefaple, Ninetales, A-Ninetales, Arcanine, Abra, Victreebel, Golem line, A-Golem line, Starmie, Magikarp, Ditto, and Mew.
I will keep updating the list, one generation at a time.
Source: Checking the DB for long periods of time