Timeline for Sieve of Eratosthenes in C# with LINQ
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 2, 2018 at 23:07 | comment | added | Rhyous | 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). | |
| Jul 27, 2016 at 13:19 | comment | added | Guffa |
@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.
|
|
| Jul 27, 2016 at 12:09 | comment | added | fubo |
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[]
|
|
| Jul 27, 2016 at 12:00 | comment | added | Guffa |
@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.
|
|
| Jul 27, 2016 at 10:13 | comment | added | fubo |
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
|
|
| Nov 30, 2011 at 14:45 | vote | accept | Eoin Campbell | ||
| Nov 17, 2011 at 14:26 | history | edited | Guffa | CC BY-SA 3.0 |
added 129 characters in body
|
| Nov 17, 2011 at 14:20 | history | answered | Guffa | CC BY-SA 3.0 |