Threshed and Malachi'd: Sieve of Eratosthenes

I took a little bit from all the answers to my previous question Threshing: Sieve of Eratosthenes.

This may be bordering on code-golfing, but I think that I have a pretty good piece of code here.

Is there any major concepts that I am overlooking, although it still seems super simple?

var upperLimit = 9999;
var primes = new List<long>();
for (var i = 3; i < upperLimit; i+=2)
{
}

for (var i = 7; i < upperLimit; i+=2)
{
foreach (var number in primes.ToList())
{
if (number == i) { continue; }
if (number % i == 0) { primes.Remove(number); }
}
}
primes.ForEach(Console.WriteLine);
Console.WriteLine("The Last Prime is " + primes[primes.Count - 1]);
Console.WriteLine("what are you waiting for? Exit the program!");


Obviously I could start off with all the primes I know by just adding them to start with and then starting my loops higher, but I think that is cheating just a little bit.

Is there any way to make this faster and able to calculate (and store) higher numbers using less memory?

-
Have you considered using uint instead of long and setting the upper limit to something dumb like uint.MaxValue? The for loops would also need to be uints. You should also definitely get rid of the List<T>.ForEach() like I mentioned on your old question. It's really bad practice. –  Magus Jul 9 '14 at 23:02
faster and able to calculate (and store) higher numbers using less memory - just wanted to point out that in general, algorithms can be made faster at the expense of using more memory, or vice versa. Which trade-off you make often depends on the circumstances, but usually it cannot be made faster and use less memory (unless it was quite naive to begin with). –  CompuChip Jul 10 '14 at 8:24
@CompuChip, that is a good point, thank you for pointing it out. –  Malachi Jul 10 '14 at 13:14
Threshed and napalm'd ;) –  Mat's Mug Jul 11 '14 at 0:10

First problem: 1 is not a prime number.

Second problem, after fixing that:

Console.WriteLine(string.Join(", ", primes.Take(10)));


2, 3, 5, 7, 9, 11, 13, 15, 17, 19

Third problem: This is not the Sieve of Eratosthenes. To quote Wikipedia (emphasis mine):

1. Create a list of consecutive integers from $2$ through $n$: $(2, 3, 4, \ldots, n)$.

2. Initially, let $p$ equal $2$, the first prime number.

3. Starting from $p$, enumerate its multiples by counting to $n$ in increments of $p$, and mark them in the list (these will be $2p$, $3p$, $4p$, etc.; the $p$ itself should not be marked).

4. Find the first number greater than $p$ in the list that is not marked. If there was no such number, stop. Otherwise, let $p$ now equal this new number (which is the next prime), and repeat from step 3.

-
there I go thinking again. I actually had to look at the definition of a prime number... (1 is not a prime number) A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself. –  Malachi Jul 10 '14 at 13:19
when I run the application 9 and 15 are not in the list. –  Malachi Jul 10 '14 at 13:20
@Malachi, mjolka is right about 9..15 with the code you have posted in your question. The problem is that your loop starts at i=7 and therefor wont check neither for 3 nor for 5. –  Heslacher Jul 10 '14 at 14:07
my original code starts at 3 instead of 7 I have removed the edit I made earlier. –  Malachi Jul 10 '14 at 14:16

This line here is horrible, terrible, and miserable:

if (number % i == 0) { primes.Remove(number); }


That one line is basically (behind the scenes) doing the following:

• scan all the data from the beginning until you find the member with the value number
• if you find that value:
• for every remaining value, shift it one back (replace each n with the value at n + 1).
• shrink the size of the List by 1.

The above is an $O(n)$ operation.

Using an indexed method to remove the value would be much faster, and a data structure like a Linked list with a $O(1)$ remove, would make a huge difference.

-
so I should be using the RemoveAt() Method then. wouldn't that still have to change the List to remove the number? I know it would be faster in finding the number, but seems like it would stillhave to  shift it one back (replace each n with the value at n + 1) and shrink the size of the List by 1 ? –  Malachi Jul 10 '14 at 13:16
Yes, the RemoveAt is also O(n), which is why I recommended a LinkeList option. The best option though would be to use a basic array, and then just mark the values as deleted.... –  rolfl Jul 10 '14 at 13:20
Very good answer, it was a tough decision on the accept... –  Malachi Jul 10 '14 at 14:02
the removal on linked list is only O(1) if you're already at the node. But you'd need to find that node first, still, going along its nodes one-by-one. You can't jump n nodes forward - and even if you could, you destroy the correspondence of place and value when you actually remove the elements instead of marking them. –  Will Ness Jul 10 '14 at 16:05
@WillNess I fail to understand the point you are making. There is no need for a correspondence of place and value, if you examine the value as is, ignoring where it stands. please don't mix up an actual sieve and the algorithm used here.. –  Vogel612 Jul 10 '14 at 16:27

List<T> is probably not the fastest data structure. A linked list would actually be perfect here. Each item keeps track of the prime after it.

Node head = new Node(1);
Node current = head.next = new Node(2);
current = current.next = new Node(3);


Then this would skip multiples of 2 and 3. You could take it further if you wanted.

for (var i = 7; i < upperLimit; i+=6)
{
current = current.next = new Node(i-2);
current = current.next = new Node(i);
}
if (i-2 < upperLimit)
current.next = new Node(i-2); //bounds correction


Then you could reduce how many i's you use by simply skipping to the next prime instead of i+=2. This is what a real sieve does and is a big slowdown for your code.

current = head.next.next; //this will get 3, since we have no factors of 1,2,3. So the loop will start at 5.
while((current = current.next) != null)
{
int num = current.data;
Node current2 = current;
while((current2 = current2.next) != null)
{
if (current2.data % num == 0)
{
current2.next = current2.next.next;
}
}
}


After this, all nodes are the prime numbers in order. You can move them to an array with a single iteration of the linked list too.

-
This is assuming you don't want to use a bitfield as proposed in one of your linked answers. If you do that you can go even faster. –  Jean-Bernard Pellerin Jul 9 '14 at 23:35
I hate to admit this, but I don't think that I have done this before, it looks like it would be fun to learn though. –  Malachi Jul 10 '14 at 13:33
Very good answer, it was a tough decision on the accept... –  Malachi Jul 10 '14 at 14:03

To make this really fast, just use an array of booleans where True means that the index is prime.

[0] False

[1] False

[2] True

[3] True

[4] False

...

When you're ready to print the primes, just go over the array.

Edit: As it wasn't clear what I mean, here is example code.

 int n = SOME_VALUE_HERE;
int N = n*n;
boolean[] isPrime = new boolean[N];

Arrays.fill(isPrime, true);
isPrime[0] = false; isPrime[1] = false;
for (int i = 2; i < N; i++)
if (isPrime[i])
for (int j = 2*i; j < N; j+=i)
isPrime[j] = false;


All the true values that are left are the primes.

-
I see two problems with this approach: 1) your maximum prime factor is Integer.MAX_VALUE` everything else is not allowed as array index. 2) It's just another trial division thing, and you run a vast amount of numbers multiple times. Also the marking of large arrays as invalid (with 2, 3, 5 as primes) is costly and "slow" –  Vogel612 Jul 10 '14 at 14:01
@Vogel612 incorrect. you can work by segments, keeping track of the value corresponding to offset 0 in the segment. And it is not trial division when all you perform is additions. See WP article's pseudocode implementation. –  Will Ness Jul 10 '14 at 16:08
@WillNess actually you seem to mix up things.. a primem $n$ can be found the easiest by examining the already found primes up to $\sqrt{n}$ and performing trial division with these. the only difference here is, with a sieve you just mark as invalid those, that are divisible by an already found prime. You are in fact not performing additions, but preventing trial divisions... or rather, the truth lies in the observer. also that segment thing is not quite clear to me.. –  Vogel612 Jul 10 '14 at 16:31
@Vogel612 I'm talking about the sieve of Eratosthenes. It is much more efficient than trial division at producing more than just a few primes, but full ranges of primes. About working at a certain range (i.e. "segment"), see this answer about "offset sieve". The usual segmented sieve works at consecutive segments, one after another, collecting primes from each sieved segment array into a separate storage (e.g. a list). –  Will Ness Jul 10 '14 at 19:06