4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$
      // 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.

\$\endgroup\$
  • \$\begingroup\$ Where did you get these magic numbers from? It would make sense with UInt16 that is converted to Int32 when done this unchecked(UInt16.MaxValue + 1) which creates an Int32 but I don't get it how it would work with Int32 that can hold numbers that are lot larger than this. \$\endgroup\$ – t3chb0t Sep 9 at 10:29
  • \$\begingroup\$ @t3chb0t, solve $$x < x^2 - 2^{32} < 2^{31}$$ \$\endgroup\$ – Peter Taylor Sep 9 at 10:34
  • \$\begingroup\$ Good point. Actually it appears to be worse than that, since the square can also overflow more than once: $$x < x^2 - k2^{32} < 2^{31}$$ for $$k = \{1, 2, 3, \dots\}$$ \$\endgroup\$ – JAD Sep 9 at 10:51
  • \$\begingroup\$ Hence "for example". \$\endgroup\$ – Peter Taylor Sep 9 at 10:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.