How to split a list in n parts so the calculation time will be equal

74 Views Asked by At

I'm trying to implement a prime number finder. It as to find primes from 0 to X. I use this algorithm (performance may be questionable but this is not the question) to find the primes :

prems.Add(3);
// Filling the list
for (int i = 5; i < numericUpDown1.Value; i += 2)
{
    nbs.Add(i);
}
// Check if the number is prime or not
foreach (int nb in nbs)
{
    bool isNotPrime = false;
    foreach (int prime in prems)
    {
        isNotPrime = nb % prime == 0;
        if (isNotPrime)
            break;
        }
        if (!isNotPrime)
            prems.Add(nb);
    }
    prems.Insert(0, 2);
}

I was working with one thread and I'm now switching to multi-thread architecture. At first I was thinking of splitting the list to browse from 1 to X/2 and from X/2 + 1 to X in order that both thread will have the same number of numbers to process. But I rapidly found out that the first thread was really faster than the other.

How can I split the list so the N thread will finish at the (almost) same time ?

By the way, I know nothing about Maths & English, so the title and the tags might be wrong, feel free to edit its.

Edit

In order to fit with multi-thread architecture, I'll compute all the primes from 1 to $\sqrt{X}$ then split the [$\sqrt{X}$;X] part in N threads.