The Sieve of Eratosthenes can be parallelised rather easily, you just have to split it into separate chunks and sieve each chunk on its own. You have started with that splitting, but haven't gone far enough to obtain good results. Let's see what problems there are in findPrimes()
var max = myTicket;
int min = max - interval +1;
int num;
var maxSquareRoot = Math.Sqrt(max);
var eliminated = new System.Collections.BitArray(max + 1);
You create a new BitArray for each thread covering all numbers from 0 to max. For the thread sieving the first chunk, that's fine, but for later threads, you're allocating much more memory than needed. With a high upper bound and many threads, that's a problem in itself, you're allocating roughly (NOOFTHREADS + 1) * limit / 2 bits where only about limit bits are needed. For fewer threads and/or lower limits, you're still deteriorating locality and will have more cache misses.
eliminated[0] = true;
eliminated[1] = true;
for (int i = 2; i < (max) / 2; i++)
You should stop the outer loop when i > maxSquareRoot. Then the loop body doesn't do anything productive anymore, it just performs one read and one or two checks. That doesn't take long for each iteration, but doing that for all i from √max to max adds up if max is e.g. 1011. Doing that for the last chunk alone can take longer than a single-threaded single-chunk sieve.
{
if (!eliminated[i])
eliminated[i] can only ever be true for i >= min (or i < 2), a situation you will only encounter in the first chunk for i <= maxSquareRoot (unless the limit is ridiculously low). So for the other chunks, you're eliminating also the multiples of 4, 6, 8, 9, 10, 12, 14, ... . A lot of wasted work.
{
if (i < maxSquareRoot)
In the case that maxSquareRoot happens to be a prime, you are not eliminating its square, the comparison ought to be <=.
{
num = ((min + i -1 )/i)*i;
if (num == i)
num = num + i;
for (int j =num; j <= max; j += i)
eliminated[j] = true;
}
}
}
Now, when the sieving is done, you step through the chunk of the BitArray
for (int b = (int)min; b < max; b++)
{
if (!eliminated[b])
lock(vals)
vals.Add(b);
}
and whenever you find a prime, you lock the list vals and add the prime to it. If there are ever two or more threads done with the sieving at about the same time, they will step on each others toes there, and the locking and waiting will slow down the process further.
To reduce space usage, each thread should create a list of the primes to maxSquareRoot, and use that to eliminate the composites in its chunk, so that the BitArray needs only max - min + 1 bits. Each thread creating its own list duplicates some work, but since the upper limit here is small, it's not much additional work. I don't know how concurrent read-access is handled, if that doesn't add synchronisation overhead, you could also work with only one list for all threads, but I doubt that would gain anything.
The code would look roughly thus:
List<int> sievePrimes = simpleSieve(maxSquareRoot);
// simpleSieve is a standard SoE returning a list of primes not exceeding its argument
var sieve = new System.Collections.BitArray(max - min + 1);
int minSquareRoot = (int)Math.Sqrt(min);
foreach(int p in sievePrimes)
{
int num = p > minSquareRoot ? p*p : ((min + p - 1)/p)*p;
num -= min;
for(; num <= max-min; num += p)
{
sieve[num] =true;
}
}
Now, to avoid the threads stepping on each others toes when adding the primes to the list, each thread should create its own list of primes and append that in one step (I'm not 100% sure that that's faster than adding each prime with its own lock, but I'd be surprised if not)
List<int> primes = new List<int>();
for(int offset = 0; offset <= max-min; ++offset)
{
if (!sieve[offset])
{
primes.Add(min + offset);
}
}
lock(vals) vals.AddRange(primes);
(and vals should be created with an initial capacity of about the expected number of primes to avoid reallocation for each chunk)
