1

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.

Community
  • 1
Thomas Ayoub
  • 1,635
  • 3
  • 12
  • 12
  • As yo ar doing trial division - isn't it necessary anyway to have the list of small primes (up to $\sqrt n$) available before another thread tries to use them? – Hagen von Eitzen Nov 03 '14 at 12:56
  • @HagenvonEitzen yes, you are right. I plan to change my algorythm for something which'll fit multi-thread architecture but I can't post it now as I haven't finished yet ;) – Thomas Ayoub Nov 03 '14 at 13:05
  • As you need to employ synchronization for each found prime anyway, I suggest that you simply chop $[1,X]$ (or $[\sqrt X,X]$ into chunks of reasonable size, but also way more tha there are threads, and the threads fetch new task-chunks when they are ready with one task ... – Hagen von Eitzen Nov 03 '14 at 13:27
  • @HagenvonEitzen please consider edit and tell me if you see a better solution for splitting ? – Thomas Ayoub Nov 04 '14 at 08:44

0 Answers0