8
\$\begingroup\$

Can someone look over this Sieve of Eratosthenes implementation? It seems almost too easy.

Rather than maintaining a seperate bit[] to track prime/not prime, I'm just removing the noncandidates from the collection completely on each iteration.

Pseudocode

LIST = 2...n

set M = 1
while M < sqrt(n)
   set M = next number in LIST > M
   remove all multiples of M (excluding M itself) from LIST

C#

int cur = 1, total = 1000;
var pc = Enumerable.Range(2, total).ToList();

while(cur <= Math.Sqrt(total))
{
    cur = pc.First(i => i > cur);
    pc.RemoveAll(i => i != cur && i % cur == 0);
}

Console.WriteLine(pc.Max());

It just seems a bit too easy. Results seem right though. In LINQPad 4

  • Runs total = 100000; in 0.008 secs
  • Runs total = 1000000; in 0.141 secs
  • Runs total = 10000000; in 2.973 secs
\$\endgroup\$
  • 2
    \$\begingroup\$ Nobody mentioned this in their answers, but Math.Sqrt() isn't the quickest of functions, and the return value used here is effectively constant. Remove it from the comparison, and assign the results to a local variable instead (which can be used in the comparison). I do not believe the compiler is smart enough to catch this... it wasn't when my flatmate tried this. \$\endgroup\$ – Clockwork-Muse Nov 17 '11 at 17:28
  • 1
    \$\begingroup\$ @X-Zero: Yes, the sqrt calculation should naturally be moved out of the loop. I already tried that, and it makes very little difference for the performance, so I just went for simplicity/close to original code in the answer. \$\endgroup\$ – Guffa Nov 17 '11 at 21:43
10
\$\begingroup\$

Yes, it works, but it's slow.

I compared it to this:

bool[] notPrime = new bool[total];
notPrime[0] = true;
notPrime[1] = true;
for (int i = 2; i <= Math.Sqrt(notPrime.Length); i++) {
  if (!notPrime[i]) {
    for (int j = i * 2; j < notPrime.Length; j += i) {
      notPrime[j] = true;
    }
  }
}

(I used Enumerable.Range(2, total - 2) in the Linq code to make it produce the numbers 2 to 99999 rather than 2 to 100001.)

For total = 100000, average for 100 executions:

Linq 27.696966 ms., 0.280000 collections
Array 0.708616 ms., 0.030000 collections

So, it takes a lot of time, and does more garbage collections.

\$\endgroup\$
  • \$\begingroup\$ one question - wouln't it be faster to skip the even values? after you had i=2 you can skip 4,6,8,10,.. by repalcing i++ with i+=2 from 3 \$\endgroup\$ – fubo Jul 27 '16 at 10:13
  • \$\begingroup\$ @fubo: It might be faster, but it's not certain as the code gets more complicated. After the first iteration all the even items in the array has already been set, so all those will be caught in the if statement in the loop. Actually, the principle of the sieve is to weed out all multiples but for all numbers, not just two. \$\endgroup\$ – Guffa Jul 27 '16 at 12:00
  • \$\begingroup\$ I've tried it and there was a minor improvement - however how about changing bool[] to System.Collections.BitArray ? .NET uses one byte to store a boolean value. I've tried total = 1.000.000.000and have a memory usage of 120MB with System.Collections.BitArray and 976MB with bool[] \$\endgroup\$ – fubo Jul 27 '16 at 12:09
  • 1
    \$\begingroup\$ @fubo: Accessing the data in the BitArray is slower, but fewer memory cache misses will make it faster, so that could go either way. If it uses too much memory you can just do multiple sieves. For each sieve you just initialise it by masking out the multiples of the prime numbers that you got this far. \$\endgroup\$ – Guffa Jul 27 '16 at 13:19
  • \$\begingroup\$ Looking at the implementation in this answer vs. the sudo code. The sudo code says j should start at i^2, but this code starts at i*2. Should the second for loop be this? for (int j = i * i; j < notPrime.Length; j += i). \$\endgroup\$ – Rhyous Jul 2 '18 at 23:07
1
\$\begingroup\$

You're accessing modified closures in your LINQ statements, so I'd copy them to locals.

        var cur = 1;
        const int Total = 1000;
        var pc = Enumerable.Range(2, Total).ToList();

        while (cur <= Math.Sqrt(Total))
        {
            var cur1 = cur;
            var cur2 = pc.First(i => i > cur1);

            pc.RemoveAll(i => i != cur2 && i % cur2 == 0);
            cur = cur2;
        }

        Console.WriteLine(pc.Max());
\$\endgroup\$
  • \$\begingroup\$ Could someone run speed tests on this? [very curious] \$\endgroup\$ – ANeves Nov 17 '11 at 17:08
  • 1
    \$\begingroup\$ Negligible on my test system. For 10000000, the average difference over 10 runs was 26ms. \$\endgroup\$ – Jesse C. Slicer Nov 17 '11 at 17:24
  • \$\begingroup\$ Wouldn't declaring cur1 and cur2 properly outside the while loop improve memory usage? \$\endgroup\$ – Stuart Blackler Nov 18 '11 at 10:38
  • 1
    \$\begingroup\$ No. They're local variables. Matters not where you declare them. \$\endgroup\$ – Jesse C. Slicer Nov 18 '11 at 12:34
1
\$\begingroup\$

update: as tested and explained by @Guffa and @EoinCampbell, this is actually much slower.

The benefits of a HashSet are mainly in access speed by index.
Since the algorithm never even accesses the list by index, the Hashset will merely introduce additional overhead with the hashing and storing of the internal structure for fast access.


I would user HashSet<int> instead of List<int>.

The only change needed would be in the while, .RemoveWhere() instead of .RemoveAll(): http://msdn.microsoft.com/en-us/library/bb361254.aspx

\$\endgroup\$
  • \$\begingroup\$ I tested that, and it takes twice as long as using a list... \$\endgroup\$ – Guffa Nov 17 '11 at 14:27
  • \$\begingroup\$ Hmm... interesting but it actually makes it significantly slower... for 10000, 100000, 1000000 the times were List = 8ms, 140ms, 3s HashSet = 30ms, 700ms , 15s \$\endgroup\$ – Eoin Campbell Nov 17 '11 at 14:41
  • \$\begingroup\$ I did not test it (#CaptainObvious) Wow, it takes so much longer?!? My universe of coding assumptions is destroyed. :( \$\endgroup\$ – ANeves Nov 17 '11 at 17:09
  • \$\begingroup\$ @ANeves: As you are looping the items in the hash set to remove them and not removing them by value, you don't get any benefit from using a hash set. \$\endgroup\$ – Guffa Nov 17 '11 at 22:39
  • \$\begingroup\$ @Guffa ... of course, I see now. Never even accessing them by value (get/set/remove), we are actually hashing all of that for nothing. Oh, I should edit the answer. [does] \$\endgroup\$ – ANeves Nov 18 '11 at 13:54
1
\$\begingroup\$

I found an answer on Stack Overflow a few days ago. I adapted it a bit to make it more parallel and easier to read.

I might have made a mistake. I tested it in my computer: Core i7 Second Gen (3GHz) with 12GB of RAM.

It took a few seconds to solve most of the numbers less than 50,000,000. However, it took around 6:32 seconds to solve 100,000,000. It took around 47 mins to solve 500,000,000. It crashed 11 hours after solving 1.5 billion.

private static void GetPrimeNumbers(int max)
{
    var allPossibleNumbers = Enumerable.Range(3, max-3);
    var possiblePrime = allPossibleNumbers
            .AsParallel()
            .Where(n => Enumerable.Range(2, (int)Math.Sqrt(n))
                                  .All(i => n % i != 0)
            )
            ;
    possiblePrime
            .ToArray()
            .AsParallel()
            .Dump()
            ;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.