为什么这个质数查找代码在迭代中产生不同的结果? [英] Why this prime number finding code is producing different results over iterations?

问题描述

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

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

问题是，它不精确.1 到 100000 之间有 9592 个质数，但我得到的值从 9588 到 9592.代码是:

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

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

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

每次迭代我都希望它返回 9592 作为结果；
为什么会这样，我该如何解决?

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

推荐答案

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

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

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

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.

这篇关于为什么这个质数查找代码在迭代中产生不同的结果?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！