Miller-Rabin Prime test (Speed is the main goal)
You could use the Sieve of Eratosthenes for numbers less than 10 million (you are only going up to 100 million).

I think that  checking the low bit (num &amp; 1) == 0 is quicker than checking the remainder num % 2 == 0.  Similarly, bit shifting is quicker for division or multiplication by 2: d /= 2 could be d &gt;&gt; 1.

You might experiment with doing an initial check for division by a few low primes (3, 5, 7, 11) in your IsPrime method and see if that makes a difference.

Finally, for your "random" numbers, you might want to choose products of primes, e.g. 3*5*7*11*13..., or maybe that plus 1.  Maybe that's crazy.  But some "random" numbers might provide richer test cases than others, and cause a faster elimination of non-primes.