Title: Use a linked list to find prime numbers in C#

I was working on a linked list liveProject for Manning the other day (I'll try to remember to post dtails when it's available), and I realized that you could use a linked list to find prime numbers. This post is related to these two, which use a different technique to build lists of primes:

• Use the Sieve of Eratosthenes to find prime numbers in C#
• Use Euler's Sieve to find prime numbers in C#

The basic idea is to generate increasingly large numbers. For each you loop through smaller numbers to see if any of them divide the new number.

One of the trickier aspects of this is that you only need to examine smaller numbers that are prime, but the sieve techniques have an issue figuring out which numbers are prime. It's not hard to tell which are prime, but you might loop through some non-primes to find them.

The linked list version builds a list of primes as it goes so it's easy to loop through them to see if they divide the new number.

Here's the algorithm:

1. Create a linked list and add 2 to it.
2. For i = 3 to however large a number you want to examine:
   1. Loop through the list so far from 2 up to the square root of i. If any of those numbers divides evenly into i, then i is not prime.
   2. If you finish the inner loop without finding a number that divides into i, then i is prime so add it to the list.

This method also gives you a new way to decide when to stop. For example, the sieve methods build a table with a maximum value so, for example, you can find the primes between 1 and 10,000. You can also do that with the linked list method. Alternatively you could find the first 10,000 primes, which would be hard with a sieve.

Here's the code with some timing statements thrown in.

private void btnGo_Click(object sender, EventArgs e) { Cursor = Cursors.WaitCursor; txtResult.Clear(); txtResult.Refresh(); lblTime.Text = ""; Cell sentinel = new Cell(); Cell last_cell = sentinel.AddAfter(2); int max = int.Parse(txtMax.Text); Stopwatch watch = new Stopwatch(); watch.Start(); for (int i = 3; i <= max; i += 2) { // See if i is prime. bool is_prime = true; int sqrt_i = (int)Math.Sqrt(i); for (Cell c = sentinel.Next; c.Value <= sqrt_i; c = c.Next) { // See if c divides evenly into i. if (i % c.Value == 0) { // c divides evenly into i so i is not prime. is_prime = false; break; } } if (is_prime) last_cell = last_cell.AddAfter(i); } watch.Stop(); lblTime.Text = "Time: " + watch.Elapsed.TotalSeconds.ToString("0.00") + " seconds"; // Display the result. StringBuilder sb = new StringBuilder(); for (Cell c = sentinel.Next; c != null; c = c.Next) { sb.Append(c.Value.ToString()); if (c.Next != null) sb.Append(" "); if (c.Value > 10000) { sb.Append("..."); break; } } txtResult.Text = sb.ToString(); Cursor = Cursors.Default; }

Overall the method is pretty fast. If you look closely at the picture at the top of the post, you can see that the program took around 0.89 seconds to find all of the prime numbers between 2 and 10 million.

Download the example to experiment with it and to see additional details.