without spending the time to make a better prime generator, you can get your test going much faster by only testing factors up till sqrt(p).

With just that change to your program, and asking for 100k primes:

{'9-1': 8829, '1-1': 4104, '9-7': 5671, '3-9': 8387, '3-7': 7419, '7-1': 6438, '1-3': 7961, '3-3': 3604, '7-9': 8022, '1-7': 8297, '7-3': 6928, '1-9': 4605, '3-1': 5596, '7-7': 3627, '9-3': 6513, '9-9': 3994}