Why this prime number finding code is producing different results over iterations?

I have a simple code that finds all prime numbers between 1 and 100000.

The problem is, it's not precise. There are 9592 primes between 1 and 100000 but I'm getting values ranging from 9588 to 9592. The code is : 

List<bool> result = new List<bool>();
Stopwatch watch = Stopwatch.StartNew();
List<Task> tasks = new List<Task>();
for (ulong i = 1; i < 100000; i++)
{


    tasks.Add(Task.Factory.StartNew(number =>
    {
        var y = (ulong)number;
        if (y == 1) return false;
        if (y == 2) return true;
        for (ulong j = 3; j < y; j++)
        {
            if (y % j == 0)
                return false;
        }
        return true;
    }, i).ContinueWith(x => result.Add(x.Result))
        );
}

Task.WaitAll(tasks.ToArray());

watch.Stop();
Console.WriteLine("done in {0}, primes {1}", watch.ElapsedMilliseconds, result.Count(x => x));

If I run this code 10 times, this is what I get : 

 done in 2764, primes 9588
 done in 2528, primes 9589
 done in 2433, primes 9591
 done in 2502, primes 9589
 done in 2400, primes 9591
 done in 2401, primes 9589
 done in 2417, primes 9591
 done in 2440, primes 9590
 done in 2423, primes 9592
 done in 2397, primes 9590

Every iteration I would expect it to return 9592 as the result;
Why is it happening this way, and how do I fix it?

Jon Skeet
people
quotationmark

You're adding to List<T> from multiple threads. That isn't supported without synchronization. If you add some locking, you may well find it works... but it would be simpler to use parallel LINQ instead. Something like this:

using System;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var primes = Enumerable.Range(1, 100000)
                               .AsParallel()
                               .Where(IsPrime)
                               .ToList();
        Console.WriteLine(primes.Count);
    }

    static bool IsPrime(int number)
    {
        if (number == 1) return false;
        // TODO: Only go up to Math.Sqrt(number)
        for (int j = 2; j < number; j++)
        {
            if (number % j == 0)
            {
                return false;
            }
        }
        return true;
    }
}

Note that I've fixed a bug in your code - your original code would make 4 a prime number, because you started the inner loop at 3 rather than 2. There's no need to special-case 2 as an input, either.

people

See more on this question at Stackoverflow