Incremental Sieve of Eratosthenes Generator

Question

So I was fiddling around with the Euler challenges. One of the things they mentioned in their discussions of the solutions is the Sieve of Eratosthenes and that you can only use it when you know an upper bound of the primes you want to generate.

I wondered whether the algorithm can be adapted to work without that upper bound. This works be replacing the bool[] for a Dictionary<int, int>. Where the original algorithm would fill all multiples immediately after finding a prime, I will fill them one at a time, keeping a dictionary to keep track of which prime has filled that value in the sieve. This way the sieve can be filled incrementally as enumeration continues.

In my version of C#, this method runs out of steam before we reach int.MaxValue, due to the increasing size of the dictionary. If I am correct, this algorithm runs in \$O(n)\$ space, and \$O(n)\$ time.

/// <summary>
/// Produce an "infinite" generator for primes.
/// </summary>
/// <remarks>Runs out of memory at prime 1_003_875_373.</remarks>
public static IEnumerable<int> Primes() {
  var sieve = new Dictionary<int, int>();
  var primeCandidate = 2;
  while (true) {
    // If sieve contains primeCandidate, it's not a prime. We retrieve its factor from the dictionary.
    if (sieve.TryGetValue(primeCandidate, out var smallestFactor)) {
      // Not needed anymore
      sieve.Remove(primeCandidate);

      // Look for the next multiple that isn't already in the sieve.
      // Unchecked because if it overflows, we don't really care, since primeCandidate would have overflowed earlier.
      unchecked {
        var nextMultiple = primeCandidate + smallestFactor;
        while (sieve.ContainsKey(nextMultiple)) {
          nextMultiple += smallestFactor;
        }
        sieve[nextMultiple] = smallestFactor;
      }
    }
    else {
      // In this case, we have found a prime. Add its square to the sieve:
      yield return primeCandidate;
      // Unchecked because if it overflows, we don't really care, since primeCandidate would have overflowed earlier.
      unchecked { sieve[primeCandidate * primeCandidate] = primeCandidate; }
    }
    // This cannot overflow!
    checked { primeCandidate++; }
  }
}

[TestMethod]
public void TestFirst20Primes() {
  var actual = Primes().Take(20).ToList();
  var expected = new[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71 };
  CollectionAssert.AreEqual(expected, actual);
}

My main concern is efficiency, both in memory and time.

Answer 1

      // Unchecked because if it overflows, we don't really care, since primeCandidate would have overflowed earlier.
      unchecked { sieve[primeCandidate * primeCandidate] = primeCandidate; }

is wrong. For example, every int in the range 65537 to 80264 inclusive overflows to a value which is greater than itself.

The easy fix is to add an overflow check. That would also fix the memory problem, because sieve would have no more entries than there are primes below 65536.