使用线程生成质数

Question

我正在尝试使用C#中的线程生成质数。用户必须输入要生成的线程数。当我运行代码时，我遇到了以下问题：

1. 有时，如果我尝试使用多个线程，我会得到“索引超出范围异常”。如果我再试一次，它就可以正常工作。
2. 每个线程都在计算相同的值。例如，如果我输入两个线程来生成2到100（包括两端）之间的质数，我会得到以下输出。

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

我已经阅读了以下帖子。但是我无法解决这些问题。我对线程概念还不熟悉。如何解决这些问题？

Simple prime number program - Weird issue with threads C#

这是我的代码:

class Program {
  const int min = 2;
  const int max = 100;
  static List<int> primes = new List<int> ();

  static void GeneratePrimes (int start, int range) {
     bool isPrime = true;
     int end = start + range;
     for (int i = start; i <= end; i++) {
        for (int j = start; j <= end; j++) {
           if (i != j && i % j == 0) {
              isPrime = false;
              break;
           }
        }
        if (isPrime) {
           primes.Add (i);
        }
        isPrime = true;
     }
  }

  static void Main (string[] args) {
     int threadCount = Convert.ToInt32 (Console.ReadLine ());
     Thread[] threads = new Thread[threadCount];
     int range = (max - min) / threadCount;
     int start = min;         
     for (int i = 0; i < threadCount; i++) {
        int startl = start;
        threads[i] = new Thread(new ThreadStart(() => GeneratePrimes(start, range)));
        startl += range;
        threads[i].Start ();            
     }
     for (int i = 0; i < threadCount; i++)
        threads[i].Join();
     PrintPrimes();
  }

  static void PrintPrimes () {
     foreach (int i in primes)
        Console.WriteLine (i);
  }
}

更新

我按照NikolayKondratyev的建议进行了更改。但是，当我使用更多的线程（>5）时，列表中出现了重复值。

- kakkarot

---

GeneratePrimes(start, range) 应该改为 GeneratePrimes(startl, range)。 - Nikolay K

为什么不直接构建一个**埃拉托斯特尼筛法**呢？ - Yeldar Kurmangaliyev

“List” 不是线程安全的。您正在没有任何锁的情况下将元素添加到 “primes” 中。 - Rob

@NikolayKondratyev 很好的发现，不过他们还需要删除 startl += range （应该改为 start += range 吗？） - Rob

C# 4.0 in a Nutshell 《C# 4.0权威指南》 - Lei Yang

Answer 1

首先问题在于您的线程起始位置 start 错误。线程创建应该是：

for (int i = 0; i < threadCount; i++) {
    var startl = start;
    threads[i] = new Thread(new ThreadStart(() => GeneratePrimes(startl, range)));
    start += range;
    threads[i].Start();
}

此外，List 不是线程安全的，应使用线程安全集合。例如，可以使用 ConcurrentQueue 及其方法 Enqueue。

此外，for 循环的条件也存在问题，应该按照以下方式编写。

for (var i = start; i < end; i++)
{
    for (var j = min; j < end; j++)
    {
        ...
    }
}

您可以通过以下方式对其进行优化：

for (var j = min; j < Math.Sqrt(end); j++)

另一个问题是您有错误的范围，因此可能存在未处理的值，因为例如对于5个线程，start + range小于max。因此，对于最后一个线程，我们需要添加(max - min)%threadCount更多的值。以下是完整代码：

class Program
{
    private const int min = 2;
    private const int max = 100;
    private static readonly ConcurrentQueue<int> primes = new ConcurrentQueue<int>();

    private static void GeneratePrimes(int start, int range)
    {
        var isPrime = true;
        var end = start + range;
        for (var i = start; i < end; i++)
        {
            for (var j = min; j < Math.Sqrt(end); j++)
            {
                if (i != j && i%j == 0)
                {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime)
            {
                primes.Enqueue(i);
            }
            isPrime = true;
        }
    }

    private static void Main(string[] args)
    {
        var threadCount = Convert.ToInt32(Console.ReadLine());
        var threads = new Thread[threadCount];
        var range = (max - min)/threadCount;
        var start = min;
        for (var i = 0; i < threadCount - 1; i++)
        {
            var startl = start;
            threads[i] = new Thread(() => GeneratePrimes(startl, range));
            start += range;
            threads[i].Start();
        }
        threads[threadCount - 1] = new Thread(() => GeneratePrimes(start, range + (max - min)%threadCount));
        threads[threadCount - 1].Start();

        for (var i = 0; i < threadCount; i++)
            threads[i].Join();
        PrintPrimes();
    }

    private static void PrintPrimes()
    {
        foreach (var i in primes)
            Console.WriteLine(i);
    }
}

- Nikolay K

---

仍然，我没有得到正确的输出。 - kakkarot

@madmax，我已经更新了我的答案，i < end 有误，应该是 i <= end。请尝试这个解决方案。 - Nikolay K

如果我只使用五个线程，那么我可以得到正确的值。但是，如果我尝试使用超过十个线程，我会得到重复的值。这是为什么？ - kakkarot

@madmax 最后一个线程的范围有问题。请看我的更新答案。i < end 没有错误。 - Nikolay K