1

（C#，prime generator）这里有一些代码，我和一个朋友正在四处寻找：

public List<int> GetListToTop(int top)
{            
    top++;
    List<int> result = new List<int>();
    BitArray primes = new BitArray(top / 2);
    int root = (int)Math.Sqrt(top);
    for (int i = 3, count = 3; i <= root; i += 2, count++)
    {
        int n = i - count;
        if (!primes[n])
            for (int j = n + i; j < top / 2; j += i)
            {
                primes[j] = true;
            }
    }
    if (top >= 2)
        result.Add(2);            
    for (int i = 0, count = 3; i < primes.Length; i++, count++)
    {
        if (!primes[i])
        {
            int n = i + count;
            result.Add(n);
        }
    }

    return result;
}

在我笨拙的 AMD x64 1800+（双核）上，所有质数低于 10 亿的质数在 34546.875 毫秒内。问题似乎是在位数组中存储更多。试图增加超过 20 亿的数据比 bitarray 想要存储的要多。关于如何解决这个问题的任何想法？

4

4 回答 4

0

我会将阵列的一部分“交换”到磁盘。我的意思是，将你的位数组分成五亿个位块并将它们存储在磁盘上。

任何时候都只有几块内存。使用 C#（或任何其他 OO 语言），应该很容易将巨大的数组封装在这个分块类中。

你会为它付出更慢的生成时间，但在我们获得更大的地址空间和 128 位编译器之前，我看不到任何解决办法。

于 2009-06-10T06:01:44.193 回答
0

或者作为 Pax 建议的替代方法，使用 .NET 4.0 中新的 Memory-Mapped File 类，让操作系统决定在任何给定时间哪些块需要在内存中。

但是请注意，您需要尝试优化算法以增加局部性，这样您就不会不必要地在内存中交换页面（比这句话听起来更棘手）。

于 2009-06-10T06:07:43.823 回答
0

使用多个 BitArray 来增加最大大小。如果一个数字要大位移并将结果存储在位数组中以存储位 33-64。

BitArray second = new BitArray(int.MaxValue);
long num = 23958923589;
if (num > int.MaxValue)
{
    int shifted = (int)num >> 32;
    second[shifted] = true;
}

long request = 0902305023;
if (request > int.MaxValue)
{
    int shifted = (int)request >> 32;
    return second[shifted];
}
else return first[request];

当然，如果 BitArray 能够支持 System.Numerics.BigInteger 的大小，那就太好了。
交换到磁盘将使您的代码非常慢。
我有一个 64 位操作系统，我的 BitArray 也仅限于 32 位。

PS：你的素数计算看起来很奇怪，我的看起来像这样：

for (int i = 2; i <= number; i++)
    if (primes[i])
        for (int scalar = i + i; scalar <= number; scalar += i)
        {
            primes[scalar] = false;
            yield return scalar;
        }
于 2010-05-04T09:13:27.493 回答
0

Sieve 算法的性能会更好。我可以在不到 4 分钟的时间内确定 int 范围内的所有 32 位素数（总共约 1.05 亿个）。当然，返回素数列表是另一回事，因为内存需求将略高于 400 MB（1 int = 4 字节）。使用 for 循环将数字打印到文件中，然后导入数据库以获得更多乐趣:) 但是对于 64 位素数，程序需要进行多次修改，并且可能需要在多个节点上分布式执行。另请参阅以下链接

http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm

http://en.wikipedia.org/wiki/Prime-counting_function

于 2010-05-21T05:59:13.153 回答