Well, maybe a small side quest: The easiest method to make the algorithm parallel might be using OpenMP:
long dividend = ...; // the number to test for primality
long limit = sqrt(test);
bool isPrime = false;
#pragma omp parallel for shared(limit,dividend,divisor,isPrime)
for (long divisor = 2; divisor <= limit; divisor++)
if (dividend % divisor == 0)
isPrime = true;
return isPrime;
You have to turn on OpenMP (something like -fopenmp) to make it run in parallel. OpenMP automatically scales with the number of cores and you can even choose a scheduling algorithm and chunk size to optimize it further. Quick testing can be done by setting OpenMP environment variables to change the defaults.
The equivalent in Qt is actually QtConcurrent. QtConcurrent::run doesn't really help because most of the work is still on your shoulders, but map-and-reduce is perfect for this. QtConcurrent actually starts a thread pool and does not oversubscribe your CPU cores (even with QtConcurrent::run). It is also not constantly starting new threads, but reuses threads from the thread pool. You can do similar things with QThread if you just start the event loop for each worker thread and push "tasks" by using QMetaObject::invokeMethod.
You might have noticed that for the OpenMP example I did not include early termination (yet). IIRC with OpenMP this is a little bit more complicated and you might have to write continue to run empty loops for "early terminations". Usually (independent of OpenMP), it is sufficient to have a boolean variable accessible to all threads and let one thread toggle it if it finds a solution. It does not have to be atomic. For early termination you probably don't care if termination is immediate or slightly delayed (until the cores have synched up). At least, you don't have to pay for the overhead of an atomic in every single loop iteration.
If you are looking for a fast solution, you can get some inspiration from Dave Plummer's Prime Drag Race. Dave Plummer is a retired Microsoft engineer on YouTube. In the Prime Drag Race people competed/compete with different programming languages to write the fastest program.
