使用LINQ生成素数

Question

以下是面试问题:

以下单行生成并显示前500个素数的列表.如何使用并行LINQ优化它,同时仍保持单个C#语句:

MessageBox.Show(string.Join(",", 
    Enumerable.Range(2, (int)(500 * (Math.Log(500) + Math.Log(System.Math.Log(500)) - 0.5)))
                .Where(x => Enumerable.Range(2, x - 2)
                                      .All(y => x % y != 0))
                .TakeWhile((n, index) => index < 500)));

我尝试引入AsParallel()以及ParallelEnumerable查询,但没有看到多核机器的任何实际好处.查询仍然使用一个CPU核心,而其他核心享受休闲时间.有人可以提出一项改进措施,将负载平均分配到所有内核上,从而缩短执行时间吗？

对于发烧友:以下公式返回一个上限,保证大于N个素数,即如果你检查这个数字,你肯定会发现小于它的N个素数:

UpperBound = N * (Log(N) + Log(Log(N)) - 0.5) //Log is natural log

Answer 1

这在我的机器上做得很好。到目前为止，我从未真正看到我的所有核心都达到 100%。谢谢你给我一个玩的借口:)

我增加了数字，直到我有足够的时间来测量（20,000）。

对我来说产生影响的关键选项是将 ExecutionMode 设置为ForceParallelism。

因为我使用 NotBuffered 合并选项，所以完成后我会重新排序。如果您不关心结果的顺序（也许您将结果放入 HashSet 中），则没有必要这样做。

DegreeOfParallelism 和 MergeOptions 仅对我的机器上的性能提供了微小的提升（如果有的话）。此示例演示如何在单个 Linq 语句中使用所有选项，这是最初的问题。

var numbers = Enumerable.Range(2, (int)(20000 * (Math.Log(20000) + Math.Log(System.Math.Log(20000)) - 0.5)))
                .AsParallel()
                .WithDegreeOfParallelism(Environment.ProcessorCount) 
                .WithExecutionMode(ParallelExecutionMode.ForceParallelism)
                .WithMergeOptions(ParallelMergeOptions.NotBuffered) // remove order dependancy
                .Where(x => Enumerable.Range(2, x - 2)
                                      .All(y => x % y != 0))
                .TakeWhile((n, index) => index < 20000);
string result = String.Join(",",numbers.OrderBy (n => n));

Answer 2

您可以仅检查值的 SQRT 来执行此操作（上面的升级代码）

var numbers = new[] {2, 3}.Union(Enumerable.Range(2, (int) (i*(Math.Log(i) + Math.Log(Math.Log(i)) - 0.5)))
                                           .AsParallel()
                                           .WithDegreeOfParallelism(Environment.ProcessorCount)
                                           // 8 cores on my machine
                                           .WithExecutionMode(ParallelExecutionMode.ForceParallelism)
                                           .WithMergeOptions(ParallelMergeOptions.NotBuffered)
                                           // remove order dependancy
                                           .Where(x => Enumerable.Range(2, (int) Math.Ceiling(Math.Sqrt(x)))
                                                                 .All(y => x%y != 0))
                                           .TakeWhile((n, index) => index < i))
                          .ToList();

但当你有一个简单且极其快速的算法时，那就太疯狂了：

private static IEnumerable<int> GetPrimes(int k)
{
    int n = (int)Math.Ceiling((k * (Math.Log(k) + Math.Log(Math.Log(k)) - 0.5)));
    bool[] prime = new bool[n + 1];
    prime[0] = prime[1] = false;
    for (int i = 2; i < prime.Length; i++)
    {
        prime[i] = true;
    }
    for (int i = 2; i*i <= n; ++i) // valid for n < 46340^2 = 2147395600
        if (prime[i])
        {
            for (int j = i*i; j <= n; j += i)
                prime[j] = false;
            yield return i;
        }
}

当然它不如 LINQ，因为它不是解决问题的时尚方法，但您应该知道它的存在。