When testing for many primes in bulk, Miller Rabin is actually quite slow. A Sieve of Eratosthenes may be faster.

But before changing your code, find out which part is slow: the prime testing, or finding the S values.