帮助理解埃拉托色筛的实现
我在这个网站上找到了eratosthenes sieve的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();
I found this LINQ implementation of the eratosthenes sieve on this website. I understand the basic concept of the sieve, but there's one detail I don't get. What is the purpose of the first 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();
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
它是运行筛子以消除列表中所有非素数的次数。
每次运行筛子时，这行代码都会获取列表中的最小数字（
结果尚未删除所有倍数的最小素数），然后删除所有倍数。这已经运行了168次，第168次列表中尚未筛选出的最小数字是997，这自然是第168个素数。这只需要运行 168 次，因为所有数字都可以表示为素数列表的乘积，并且没有小于 1000000 的数字是第 169 个素数 (1,009) 的倍数，而不是 a 的倍数低于 1009 的素数。通过筛选出尚未删除的 1009 可以删除的最低数字是
1009 * 1013 = 1,022,117，即第 169 个素数乘以第 170 个素数，显然大于 100000，因此不需要检查这组数字。因此，当您到达该点时，1009 的所有倍数都已从列表中删除，因此没有必要继续，因为您已经从列表中删除了所有非素数。 ：D
It is the number of times the sieve will be run to eliminate all non-primes from the list.
Each time you run the sieve, this line of code takes the smallest number in the list (the smallest prime that the
resulthasn't had all its multiples removed of yet) and then removes all the multiples. This is run 168 times, and on the 168th time the smallest number the list hasn't been screened of yet is 997, which naturally is the 168th prime.This only needs to be run 168 times because all numbers can be expressed as the product of a list of primes, and there is no number less than 1000000 that is a multiple of the 169th primes number (1,009) that is NOT a multiple of a prime lower than 1009. The lowest number that this would removed by sieving out 1009 that has NOT been removed already is
1009 * 1013 = 1,022,117, or the 169th primes multiplied by the 170th prime, which is clearly greater than 100000 and thus doesn't need to be checked for this set of numbers.Hence, all the multiples of 1009 have already been removed from the list when you get to that point, so there's no point in continuing as you already have removed all the non-primes from the list. :D
小于 1000 的素数有 168 个。
如果
x小于1,000,000，且x不是素数，则x> 可以因式分解为质数p1, p2, ..., pn。这些因素中至少有一个必须小于1000，否则乘积将大于1,000,000。这意味着至少有一个因数必须是前 168 个素数之一。There are 168 primes less that 1000.
If
xis less than1,000,000, andxis not prime, thenxcan be factored into prime numbersp1, p2, ..., pn. At least one of these factors must be less that1000, or else the product would be more than1,000,000. This means at least one factor must be one of the first 168 primes.