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，等等）。

然後，當這些數組變得真的太大以至於內存不足時，您可以將它們一次一個地保存到磁盤和加載中，這是您需要的一種（顯然這會比內存中訪問慢很多，幸運的是，應該與上一次相同的陣列，所以如果你保持它，這將有助於）。

通過保持結果在內存中的大列表中保留所有結果，也會給自己造成麻煩。你最好把它們寫到磁盤（也許在屏幕上），當你找到它們，然後不把它們留在內存中。