-1
 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 素数。

先感谢您。

4

1 回答 1

1

关键限制是您必须保留大量布尔值。您可能正在违反数组大小的限制;尝试使用多个数组,而不是正确的数组。您可以编写函数使其像数组一样易于使用,但在幕后它由多个数组支持(可能一个用于 0-1 百万的数字,另一个用于 1mio-2mio 等)。

然后,当这些数组对于内存来说太大时,您可以将它们保存到磁盘并加载,一次一个,您需要的一个(显然这将比内存访问慢得多。幸运的是,许多访问应该是与上次相同的数组,因此如果您保留它会有所帮助)。

通过将结果素数全部保存在内存中的一个大列表中,您也会给自己带来麻烦。您最好在找到它们时将它们写入磁盘(也许在屏幕上),然后不要将它们保存在内存中。

于 2013-05-11T02:15:18.717 回答