4

我在这个网站上找到了 Eratosthenes 筛子的 LINQ 实现。我了解筛子的基本概念，但有一个细节我不明白。第一个 Enumerable.Range(0,168) 的目的是什么？

List<int> erathostheness = Enumerable.Range(0, 168)
.Aggregate(Enumerable.Range(2, 1000000).ToList(), (result, index) =>
{
    result.RemoveAll(i => i > result[index] && i % result[index] == 0);
    return result;
}).ToList();
4

2 回答 2

3

它是运行筛子以从列表中消除所有非素数的次数。

result.RemoveAll(i => i > result[index] && i % result[index] == 0);

每次运行筛子时，这行代码都会取列表中的最小数字（result尚未删除所有倍数的最小素数），然后删除所有倍数。这运行了 168 次，第 168 次列表中尚未筛选的最小数字是 997，这自然是第 168 个素数。

这只需要运行 168 次，因为所有数字都可以表示为素数列表的乘积，并且没有小于 1000000 的数字是第 169 个素数 (1,009) 的倍数，它不是 a 的倍数低于 1009 的素数。通过筛选出尚未被移除的 1009 来移除的最小数是1009 * 1013 = 1,022,117，或者第 169 个素数乘以第 170 个素数，这显然大于 100000，因此不需要检查这组数字。

因此，当您到达该点时，所有 1009 的倍数都已从列表中删除，因此没有必要继续，因为您已经从列表中删除了所有非素数。:D

于 2011-05-22T16:01:48.147 回答
2

少于 1000 个的素数有 168 个。

如果x小于1,000,000且x不是素数，则x可以分解为素数p1, p2, ..., pn。这些因素中至少有一个必须小于1000，否则产品会大于1,000,000。这意味着至少一个因子必须是前 168 个素数之一。

于 2011-05-22T15:51:29.303 回答