Finding the 10001st prime in C# In an effort to learn  C# / improve my coding skills, I've started working on the Project Euler problems. I see that I may have been overthinking things a bit after finishing problem 7:


  By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can
  see that the 6th prime is 13.
  
  What is the 10 001st prime number?


But even so I believe that my solution should be faster than what is presented in the problem overview. While this may not be an issue when searching for a "small" number of primes, the previous problems have focused quite a bit on optimizing the codes so I am wondering if I have missed something  obvious.

In other words, how does my code compare to the pseudocode presented in the overview of the problem? Are there any obvious mistakes I make in my code?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;

namespace ProjectEulerTasks
{
    class Program
    {
        static void Main(string[] args)
        {
            int no_of_primes_found = 0;
            int current_number = 0;
            List&lt;int&gt; found_primes = new List&lt;int&gt;();
            bool n_minus_found = false;
            bool n_plus_found = false;

            found_primes.Add(2);
            found_primes.Add(3);
            found_primes.Add(5);
            found_primes.Add(7);
            found_primes.Add(11);
            found_primes.Add(13);

            current_number = 12;
            no_of_primes_found = 6;

            while (no_of_primes_found &lt; 10001)
            {
                current_number += 6;
                n_minus_found = false;
                n_plus_found = false;
                foreach (int current_prime in found_primes)
                {
                    if (!n_minus_found &amp;&amp; (current_number - 1) % current_prime == 0)
                    {
                        n_minus_found = true;
                    }
                    if (!n_plus_found &amp;&amp; (current_number + 1) % current_prime == 0)
                    {
                        n_plus_found = true;
                    }
                    if (n_minus_found &amp;&amp; n_plus_found)
                    {
                        break;
                    }
                }
                if (!n_minus_found)
                {
                    found_primes.Add(current_number - 1);
                    no_of_primes_found = no_of_primes_found + 1;
                }
                if (!n_plus_found &amp;&amp; no_of_primes_found &lt; 10001)
                {
                    found_primes.Add(current_number + 1);
                    no_of_primes_found = no_of_primes_found + 1;
                }
            }
            System.Diagnostics.Debug.Print(Convert.ToString(no_of_primes_found));
            System.Diagnostics.Debug.Print(Convert.ToString(found_primes[found_primes.Count - 1]));
        }
    }
}


Project Euler pseudocode:
Your solution looks massively overcoded and woefully under-engineered - as if you had fixed on one particular solution facet (striding in the manner of the mod 6 wheel with unrolling of one revolution) of a particular approach (trial division) before analysing the problem.

Also, you didn't specify with regard to which quality you want your code to be compared to others. It is way too convoluted for scoring on elegance and simplicity, and it is way too slow for scoring on speed. Hence it is impossible to guess what you think its merit might be...

You obviously overlooked the bit about only scanning up to the square root of the current number in the pseudo code. This alone makes your code run much more slowly than the simplest, cleanest, most straightforward algorithm without any optimisations whatsoever. In other words, all that nonsense with wheeled striding and unrolling is for nought. 

To answer your question: compared to the pseudo code your solution does not fare well at all.

If you are looking for speed in contexts that involve the enumeration of non-trivial numbers of primes then you might want to look at sieves. The Sieve of Eratosthenes is simple but offers an unbeatable bang for buck ratio. 

For the piddling small numbers that Project Euler tasks deal in, I'd recommend going for simplicity, cleanness and elegance. At least that will give you are more thorough understanding of the algorithms. Forget all the half-understood supposed optimisations that you may have seen somewhere. They are only optimisations if they are needed, applicable, and applied correctly. In all other cases they are pessimisations, and they also keep you from understanding your own code, obviously. 

Start simple. Measure. Add complications one by one and measure the effect.

Also, the work that is done fastest is the work that you don't do at all. Hence it always pays to look at a problem with an eye for opportunities not to do things. This includes donning first the glasses of the mathematician, then those of the algorithmist, and only last the loupe of the performance coder.

Answer to eirikdaude's question in the comment (posted here to give it space): 

Wheeled striding can cut the workload by a certain (small) constant factor, by way of skipping a certain part of the numbers to be scanned. 

Double striding cuts the load in half by skipping multiples of two; mod 6 striding skips a further third, mod 30 (2*3*5) striding a further fifth, and so on. 

Effectiveness decreases as you add more small primes and the effort increases explosively. Double striding has the best bang-for-buck ratio in many cases, and it has other advantages (like regular strides, as opposed to the 2,4,2,4 step of the mod 6 wheel or the 48 step sequence of the mod 210 wheel). Higher wheel orders than 2 require careful coding and engineering to realise at goodish part of the theoretical speedup. Even the highest-order wheel with the most perfect coding can realise only a small constant speedup, typically not more than half an order of magnitude (without even considering the slow-down due to the much more complex code).



The column 'modulus' gives the wheel circumference, 'spokes' gives the number of hops in an increment sequence, 'ratio' gives the ratio of how many numbers need to be scanned compared to scanning all candidates. 

The mod 30 wheel has a lot of nice advantages (starting with the fact that it maps nicely to eight-bit bytes) but cannot even double the performance of the mod 2 wheel, despite all the effort required for implementing it. Mod 210 wheels are occasionally found in heavy-duty industrial-grade code, and wheels higher than 13 (starting with 17, i.e. mod 510,510) definitely belong in the pyrrhic oddball category. 

Use the 'ratio' column to gauge the limit on possible speedups due to workload reduction, and use the 'spokes' column to gauge the required code complexity (unrollings, sizes of lookup tables etc.). 

Have a look at my answer in the topic Printing all the prime numbers between two bounds to see benchmarks for actual speedups gained from wheeled striding in a roughly similar setting. Compare actual speedups to the theoretical limits gleaned from the table, to the increase in code complexity despite the tricks employed, and how little this all accomplishes compared to algorithmic optimisations. 

Morale: outside of academic papers, wheels can give you only a small constant boost.

On the other hand, scanning only candidate factors up to the square root of the current number instead of all candidates gives exponential benefits, several orders of magnitude already with the small Euler target (100001st prime).

I found it very rewarding to treat the Euler problems with respect, giving them the full math ponderation and pencil+paper preparation before throwing down the first line of code - and then striving for the simplest-possible, cleanest, most elegant code that I can manage (some might say this comes a couple decades too late, and they might not be entirely wrong about that...).