How can I make this prime finder operate in parallel

Question

I know prime finding is well studied, and there are a lot of different implementations. My question is, using the provided method (code sample), how can I go about breaking up the work? The machine it will be running on has 4 quad core hyperthreaded processors and 16GB of ram. I realize that there are some improvements that could be made, particularly in the IsPrime method. I also know that problems will occur once the list has more than int.MaxValue items in it. I don't care about any of those improvements. The only thing I care about is how to break up the work.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Prime
{
    class Program
    {
        static List<ulong> primes = new List<ulong>() { 2 };

        static void Main(string[] args)
        {
            ulong reportValue = 10;
            for (ulong possible = 3; possible <= ulong.MaxValue; possible += 2)
            {
                if (possible > reportValue)
                {
                    Console.WriteLine(String.Format("\nThere are {0} primes less than {1}.", primes.Count, reportValue));

                    try
                    {
                        checked
                        {
                            reportValue *= 10;
                        }
                    }
                    catch (OverflowException)
                    {
                        reportValue = ulong.MaxValue;
                    }
                }

                if (IsPrime(possible))
                {
                    primes.Add(possible);
                    Console.Write("\r" + possible);
                }
            }

            Console.WriteLine(primes[primes.Count - 1]);
            Console.ReadLine();
        }

        static bool IsPrime(ulong value)
        {
            foreach (ulong prime in primes)
            {
                if (value % prime == 0) return false;
                if (prime * prime > value) break;
            }

            return true;
        }
    }
}

There are 2 basic schemes I see: 1) using all threads to test a single number, which is probably great for higher primes but I cannot really think of how to implement it, or 2) using each thread to test a single possible prime, which can cause a non-continuous string of primes to be found and run into unused resources problems when the next number to be tested is greater than the square of the highest prime found.

To me it feels like both of these situations are challenging only in the early stages of building the list of primes, but I'm not entirely sure. This is being done for a personal exercise in breaking this kind of work.

Answer 1

Use the sieve of Eratosthenes instead. It's not worthwhile to parallelize unless you use a good algorithm in the first place.

Separate the space to sieve into large regions and sieve each in its own thread. Or better use some workqueue concept for large regions.

Use a bit array to represent the prime numbers, it takes less space than representing them explicitly.

See also this answer for a good implementation of a sieve (in Java, no split into regions).

Answer 2

If you want, you can parallelize both operations: the checking of a prime, and the checking of multiple primes at once. Though I'm not sure this would help. To be honest I'd consider remove the threading in main().

I've tried to stay faithful to your algorithm, but to speed it up a lot I've used x*x instead of reportvalue; this is something you could easily revert if you wish.

To further improve on my core splitting you could determine an algorithm to figure out the number of computations required to perform the divisions based on the size of the numbers and split the list that way. (aka smaller numbers take less time to divide by so make the first partitions larger)

Also my concept of threadpool may not exist the way I want to use it

Here's my go at it(pseudo-ish-code):

List<int> primes = {2};  
List<int> nextPrimes = {};
int cores = 4;
main()
{   
  for (int x = 3; x < MAX; x=x*x){  
    int localmax = x*x;
    for(int y = x; y < localmax; y+=2){  
      thread{primecheck(y);}
    }
  "wait for all threads to be executed"
  primes.add(nextPrimes);
  nextPrimes = {};
  }
}

void primecheck(int y)
{  
  bool primality;  
  threadpool? pool;
  for(int x = 0; x < cores; x++){
    pool.add(thread{
      if (!smallcheck(x*primes.length/cores,(x+1)*primes.length/cores ,y)){
        primality = false;
        pool.kill();
      }
    });
  }  
  "wait for all threads to be executed or killed"
  if (primality)
    nextPrimes.add(y);  
}

bool smallcheck(int a, int b, int y){  
  foreach (int div in primes[a to b])  
    if (y%div == 0)  
      return false;  
  return true;
}

E: I added what I think pooling should look like, look at revision if you want to see it without.