title: C#: How to make Sieve of Atkin incremental
body: <p>I don't know if this is possible or not, but I just gotta ask. My mathematical and algorithmic skills are kind of failing me here :P</p>
  
  <p>The thing is I now have this class that generates prime numbers up to a certain limit:</p>
  
  <pre><code>public class Atkin : IEnumerable&lt;ulong&gt;
  {
      private readonly List&lt;ulong&gt; primes;
      private readonly ulong limit;
  
      public Atkin(ulong limit)
      {
          this.limit = limit;
          primes = new List&lt;ulong&gt;();
      }
  
      private void FindPrimes()
      {
          var isPrime = new bool[limit + 1];
          var sqrt = Math.Sqrt(limit);
  
          for (ulong x = 1; x &lt;= sqrt; x++)
              for (ulong y = 1; y &lt;= sqrt; y++)
              {
                  var n = 4*x*x + y*y;
                  if (n &lt;= limit &amp;&amp; (n % 12 == 1 || n % 12 == 5))
                      isPrime[n] ^= true;
  
                  n = 3*x*x + y*y;
                  if (n &lt;= limit &amp;&amp; n % 12 == 7)
                      isPrime[n] ^= true;
  
                  n = 3*x*x - y*y;
                  if (x &gt; y &amp;&amp; n &lt;= limit &amp;&amp; n % 12 == 11)
                      isPrime[n] ^= true;
              }
  
          for (ulong n = 5; n &lt;= sqrt; n++)
              if (isPrime[n])
              {
                  var s = n * n;
                  for (ulong k = s; k &lt;= limit; k += s)
                      isPrime[k] = false;
              }
  
          primes.Add(2);
          primes.Add(3);
          for (ulong n = 5; n &lt;= limit; n++)
              if (isPrime[n])
                  primes.Add(n);
      }
  
  
      public IEnumerator&lt;ulong&gt; GetEnumerator()
      {
          if (!primes.Any())
              FindPrimes();
  
          foreach (var p in primes)
              yield return p;
      }
  
  
      IEnumerator IEnumerable.GetEnumerator()
      {
          return GetEnumerator();
      }
  }
  </code></pre>
  
  <p>Now, what I would like is to get rid of the limit so that the sequence would never stop (theoretically).</p>
  
  <p>I am thinking it could go something like this:</p>
  
  <ol>
  <li>Start with some trivial limit
  
  <ul>
  <li>Find all the primes up to the limit</li>
  <li>Yield all the newfound primes</li>
  <li>Increase the limit (by doubling or squaring the old limit or something like that)</li>
  <li>Goto step 2</li>
  </ul></li>
  </ol>
  
  <p>And optimally that step two should only have to work between the old limit and the new one. In other words it shouldn't have to find the lowest primes again and again.</p>
  
  <p>Is there a way this can be done? My main problem is that I don't quite understand what <code>x</code> and <code>y</code> for example is in this algorithm. Like, could I just use the same algorithm kind of but set <code>x</code> and <code>y</code> to <code>oldLimit</code> (initially 1) and run it up to <code>newLimit</code>? Or how would that work? Any bright minds with some light to shed on this?</p>
  
  <p>The point of this is so that I won't have to set that limit. So that I can for example use Linq and just <code>Take()</code> however many primes I need, not worrying about if the limit is high enough, et cetera.</p>