为什么这个素数查找代码在迭代过程中会产生不同的结果？

Question

我有一个简单的代码可以找到 1 到 100000 之间的所有素数。

问题是，它不准确。 1 到 100000 之间有 9592 个素数，但我得到的值范围是 9588 到 9592。代码是：

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));

如果我运行此代码 10 次，这就是我得到的：

 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

我希望每次迭代的结果都是 return 9592；
为什么会这样，我该如何解决？

Answer 1

您正在从多个线程添加到 List<T>。如果没有同步，则不支持。如果您添加一些锁定，您可能会发现它有效……但使用并行 LINQ 会更简单。像这样：

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;
    }
}

请注意，我已经修复了您的代码中的一个错误 - 您的原始代码会使 4 成为质数，因为您从 3 而不是 2 开始了内部循环。没有必要将特殊情况 2 作为输入, 要么.

Answer 2

您可以使用 parallel LINQ (PLINQ) 代替 @Jon Skeet 所说的。像这样：

private int DoParallel(int first,int max)
{
     var numbers = Enumerable.Range(first, max - 9);
     var parallelQuery = numbers.AsParallel()
                        .Where(n => Enumerable.Range(2, (int)Math.Sqrt(n))
                        .All(i => n % i != 0));
     return parallelQuery.Count();
}

为什么这个素数查找代码在迭代过程中会产生不同的结果？

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

c#

task