C＃素数发生器内存不足

Question

public class Atkin_Algo : IEnumerable<ulong> 
{ 
     private List<ulong> primes; 
     private ulong limit; 

     public Atkin_Algo(ulong _limit) 
     { 
      limit = _limit; 
      primes = new List<ulong>(); 
     } 

     public IEnumerator<ulong> GetEnumerator() 
     { 
      if (!primes.Any()) 
       Find_Primes(); 

      foreach (var p in primes) 
       yield return p; 
     } 

     IEnumerator IEnumerable.GetEnumerator() 
     { 
      return GetEnumerator(); 
     } 

     private void Find_Primes() 
     { 
      var is_prime = new bool[limit + 1]; 
      var sqrt = Math.Sqrt(limit); 

      for (ulong x = 1; x <= sqrt; x++) 
      { 
       for (ulong y = 1; y <= sqrt; y++) 
       { 
        var n = 4 * x * x + y * y; 
        if (n <= limit && (n % 12 == 1 || n % 12 == 5)) 
        { 
          is_prime[n] ^= true; 
        } 

        n = 3 * x * x + y * y; 
        if (n <= limit && n % 12 == 7) 
        { 
          is_prime[n] ^= true; 
        } 

        n = 3 * x * x - y * y; 
        if (x > y && n <= limit && n % 12 == 11) 
        { 
          is_prime[n] ^= true; 
        } 
       } 
      } 

      for (ulong n = 5; n <= sqrt; n++) 
      { 
       if (is_prime[n]) 
       { 
        var s = n * n; 
        for (ulong k = s; k <= limit; k += s) 
        { 
          is_prime[k] = false; 
        } 
       } 
      } 

      primes.Add(2); 

      primes.Add(3); 

      for (ulong n = 5; n <= limit; n += 2) 
      { 
       if (is_prime[n]) 
       { 
        primes.Add(n); 
       } 
      } 
     } 
} 

所以我的问题是当我想生成一个大的列表我得到OutOfMemoryException这是预期的，但我想能够解决这个问题。我没有做任何这样的事情之前，任何意见将不胜感激。

我想避免这个问题的原因是很快就会使用BigInteger类并能够生成大量素数。

预先感谢您。

Answer 1

关键的限制是大量的布尔，你必须保持。你可能会违背数组大小的限制;而不是一个适当的数组，尝试使用多个数组。您可以编写函数使其与数组一样易于使用，但在幕后它由多个数组支持（可能一个用于0-1百万的数字，另一个用于1mio-2mio，等等）。

然后，当这些数组变得真的太大以至于内存不足时，您可以将它们一次一个地保存到磁盘和加载中，这是您需要的一种（显然这会比内存中访问慢很多，幸运的是，应该与上一次相同的阵列，所以如果你保持它，这将有助于）。

通过保持结果在内存中的大列表中保留所有结果，也会给自己造成麻烦。你最好把它们写到磁盘（也许在屏幕上），当你找到它们，然后不把它们留在内存中。