c#素数生成器内存不足
本文关键字:内存不足 | 更新日期: 2023-09-27 18:13:16
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类并能够生成大素数。
提前感谢。
关键的限制是必须保持大量的bool数组。你可能会碰到数组大小的限制;尝试使用多个数组而不是正确的数组。您可以编写函数使其像数组一样易于使用,但在幕后,它由多个数组支持(可能一个用于0- 100万的数字,另一个用于100万- 200万的数字,等等)。
然后,当这些数组变得太大,内存无法容纳时,您可以将它们保存到磁盘并加载,一次加载一个,您需要的一个(显然,这将比内存访问慢得多)。幸运的是,许多访问应该是与上次相同的数组,所以如果您保留它,将会有所帮助)。
将结果素数保存在内存中的一个大列表中也会给自己带来麻烦。当您找到它们时,最好将它们写入磁盘(或者在屏幕上),然后不要将它们保存在内存中。