帮助了解eratosthenes网筛的实施情况

我在这个网站上发现了这个LINQ网关的eratosthenes网筛的实施。我理解筛的基本概念，但是我没有看到一个细节。第一个Enumerable.Range（0,168）的目的是什么？帮助了解eratosthenes网筛的实施情况

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

来源

2011-05-22 Dan

这是**而不是Eratosthenes **的Sieve，它只会使用添加来从数组中剔除合成数字; **这是一个试验部分总理筛**，因为它通过试验分区消除了一定范围内的合成数并测试了非零余数。它是一种优化版本，因为它只能被找到的素数所区分。它不是一个精确的优化，因为它需要至少估计直到该范围的平方根的质数（因为范围1000000中的质数为1000到1000）。更好的版本是[这里]（http://stackoverflow.com/a/1510186/549617）。 – GordonBGood 2014-04-30 07:41:17

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

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

每次运行时筛，这行代码需要在列表中最小的数字，然后删除所有的倍数（该result一直没有它的倍数的去除尚未最小素数）。这是168次，而在第168次时，尚未筛选出的最小号码是997，这自然是168号。

此只需要运行，因为所有的数字可以表示为质数的列表的产品168次，而且没有数量少超过100万也就是169质数号（1009）的倍数，即不一个低于1009的素数的倍数。通过筛出1009而未被移除的最低数字是1009 * 1013 = 1,022,117，或者是第169个素数乘以第170个素数，这显然大于100000，因此不会需要检查这组数字。

因此，当你到达那个点时，所有1009的倍数已经从列表中删除，所以没有必要继续，因为你已经从列表中删除了所有的非素数。：D

来源

2011-05-22 16:01:48

）我们如何推广这个代码来找出所有小于n的素数？在这种情况下168的值是多少？ – Raj 2013-07-25 23:22:03

@Raj替换'1000000'用'n'代替，并用'sqrt（n）'计算[主要计数函数]（http://www.wikipedia.org/wiki/Prime-counting_function）代替168 TLDR：对于'x> = 17' ，'1.25506 * x /（log（x））'将大于素数计数函数，所以你可以使用它（当然用'x = sqrt（n）'）。 – 2013-07-26 02:29:19

有168个质数小于1000

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

来源

2011-05-22 15:51:29

谢谢，A +。你碰巧知道为什么或有一个来源为什么这是？ – Dan 2011-05-22 15:55:53

@丹，我更新了我的答案。如果还不清楚，你能指出我需要详细说明的部分吗？ – 2011-05-22 15:59:10

谢谢，希望我能给出2个正确的答案... :( – Dan 2011-05-22 16:15:31

帮助了解eratosthenes网筛的实施情况

回答

相关问题