[adgjlsfhk1]

IMO you really shouldn't be bottle-necked by random number generation speed. If the kernel calls are what's slowing you down, you could use a strong user space PRNG (e.g. aes based) that is seeded with urandom. The other approach that would be not perfect but a lot better would be to re-randomize the lower 64 or 128 bits each time. That would cut down your rng requirements by a factor of ~10 while keeping much better uniformity since your jumps would be random and much bigger than the gap between primes.