素数的求和使用筛后仍然缓慢 [英] prime number summing still slow after using sieve
问题描述
我在下面的一个项目欧拉编码挑战一展身手，在代码中给出的答案是正确的，但我不明白为什么它采取将近一分钟跑。将其用之前使用筛相似次精加工。其他用户也报告时间缩短到毫秒。
我以为我想提出一个基本的错误的地方...
//的素数低于10总和为2 + 3 + 5 + 7 = 17，
//见以下两个万支全素数的总和。
公共静态长Ex010（）
{
VAR总和= 0L;
变种筛=新布尔[2000000]
无功素数=新的List< INT>（10000）;
的for（int i = 2; I< sieve.Length;我++）
{
如果（筛[I-1]）$ B $ B继续;
VAR isPrime = TRUE;
的foreach（在素数VAR素数）
{
如果（I％黄金== 0）{
isPrime = FALSE;
中断;
}
}
如果（isPrime）{
primes.Add（ⅰ）;
总和+ =我;
为（VAR X = 1 * 2; X< sieve.Length; X + = 1）{
筛[X-1] =真;
}
}
}
返回总和;
}
修改
这似乎唯一缺少的就是这种优化：
如果（黄金>的Math.sqrt（I））
断点;
它带来的时间缩短到160毫秒。
修改2：
最后点击，拿出的foreach的建议了很多次。它现在是12毫秒。最终的解决方案：
公共静态长Ex010（）
{
VAR总和= 0L;
变种筛=新布尔[2000000]
的for（int i = 2; I< sieve.Length;我++）
{
如果（筛[I-1]）$ B $ B继续;
总和+ =我;
为（VAR X = 1 * 2; X< sieve.Length; X + = 1）{
筛[X-1] =真;
}
}
返回总和;
}
您正在做的试验师除了筛子。结果
布尔数组已经告诉你，如果一个数是素数，所以你不需要的素数的名单都没有。结果
你也可以加快速度同比仅筛选到了极限的平方根。结果
如果你想节省一些内存也可以使用的 BitArray 而不是一个布尔数组。
公共静态长Ex010（）
{
const int的限位= 2000000;
INT开方=（INT）的Math.sqrt（限制）;
VAR总和= 0L;
变种isComposite =新布尔[限于]
的for（int i = 2; I<开方;我++）{$ B $ B如果（isComposite [我 - 2]）
继续; //这个数是不是素数，跳过
总和+ =我;
为（VAR X = I * I; X< isComposite.Length; X + = 1）{
isComposite [X - 2] =真;
}
}
//添加余下的素数
的for（int i =开方; I<限制;我++）{$ B $ B如果（isComposite [我！ - 2]）{
总和+ =我;
}
}
返回总和;
}
I had a go at a project euler coding challenge below, the answer given by the code is correct but I do not understand why its taking nearly a minute to run. It was finishing with similar times prior to using a sieve. Others users are reporting times as low as milliseconds.
I assume I am making a basic error somewhere...
// The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
// Find the sum of all the primes below two million.
public static long Ex010()
{
var sum = 0L;
var sieve = new bool[2000000];
var primes = new List<int>(10000);
for (int i = 2; i < sieve.Length; i++)
{
if (sieve[i-1])
continue;
var isPrime = true;
foreach (var prime in primes)
{
if (i % prime == 0) {
isPrime = false;
break;
}
}
if (isPrime) {
primes.Add(i);
sum += i;
for (var x = i * 2; x < sieve.Length; x += i) {
sieve[x-1] = true;
}
}
}
return sum;
}
EDIT:
The only thing that seemed missing was this optimization :
if (prime > Math.Sqrt(i))
break;
It brings the time down to 160 ms.
EDIT 2:
Finally clicked, took out the foreach as was suggested many times. Its now 12 ms. Final solution :
public static long Ex010()
{
var sum = 0L;
var sieve = new bool[2000000];
for (int i = 2; i < sieve.Length; i++)
{
if (sieve[i-1])
continue;
sum += i;
for (var x = i * 2; x < sieve.Length; x += i) {
sieve[x-1] = true;
}
}
return sum;
}
You are doing trial division in addition to a sieve.
The boolean array will already tell you if a number is prime, so you don't need the List of primes at all.
You can also speed it up by only sieving up to the square root of the limit.
If you want to save some memory also, you can use a BitArray instead of a boolean array.
public static long Ex010()
{
const int Limit = 2000000;
int sqrt = (int)Math.Sqrt(Limit);
var sum = 0L;
var isComposite = new bool[Limit];
for (int i = 2; i < sqrt; i++) {
if (isComposite[i - 2])
continue;//This number is not prime, skip
sum += i;
for (var x = i * i; x < isComposite.Length; x += i) {
isComposite[x - 2] = true;
}
}
//Add the remaining prime numbers
for (int i = sqrt; i < Limit; i++) {
if (!isComposite[i - 2]) {
sum += i;
}
}
return sum;
}
这篇关于素数的求和使用筛后仍然缓慢的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
