C# Prime Number Generator Out of Memory

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); 
       } 
      } 
     } 
} 

Так что моя проблема в том, когда я хочу создать LARGE-список. Я получаю OutOfMemoryException, которого можно ожидать, но я хочу иметь возможность обойти это. Я не делал ничего подобного, прежде чем кто-либо из советов будет очень благодарен.

Причина, по которой я хочу избежать этой проблемы, - это скоро использовать класс BigInteger и иметь возможность генерировать LARGE простые числа.

Заранее спасибо.

Answer 1

Ключевым ограничением является большой массив bools, который вы должны соблюдать. Вероятно, вы используете ограничение по размеру массива; вместо правильного массива, попробуйте использовать несколько массивов. Вы можете писать функции, чтобы сделать его максимально простым в использовании в качестве массива, но за кулисами его поддерживают несколько массивов (возможно, один для чисел от 0 до 1 миллиона, другой для 1mio-2mio и т. Д.).

Затем, когда эти массивы становятся слишком большими для памяти, вы можете сохранять их на диск и загружать по одному, то, что вам нужно (очевидно, это будет намного медленнее, чем доступ в память. К счастью, многие обращения должен быть в том же массиве, что и в прошлый раз, поэтому, если вы его сохраните, это поможет).

Вы также вызываете проблемы для себя, сохраняя результат простым в большом списке в памяти. Вам лучше писать их на диск (и, возможно, на экране), как вы их находите, а затем не хранить их в памяти.