C＃发电机首相，麻杏出位阵列

Question

（C＃，素发生器） 下面有一些代码的朋友和我周围戳：

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 64 1800+（双核），用于在34546.875ms低于1十亿所有素数。问题似乎是存储更多的比特阵列英寸试图曲柄超过20亿〜超过了bitarray希望存储。如何让周围的任何想法？

Answer 1

我将所述阵列的“交换”份到磁盘。到那个，我的意思是，将你的位阵列成半十亿比特块，并将其存储在磁盘上。

在具有存储器在任何一个时间只有几个块。用C＃（或任何其它面向对象的语言），它应易于封装这个组块类中的巨大阵列。

您会为它付出与较慢的生成时间，但我没有看到周围的任何方式，直到我们得到更大的地址空间和128位编译器。

Answer 2

或作为其替代方式以一个由大同建议的，使用新的内存映射文件的类在.NET 4.0和让OS决定哪些块需要在存储器在任何给定时间。

然而

请注意，你会想尝试和优化算法，以增加地方，这样你就不会不必要最终进出内存交换页（棘手比这一句话使得它听起来）。

Answer 3

使用多个BitArrays增加的最大大小。如果一个数字是大位移它并将结果以位阵列存储，用于存储比特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;
        }

Answer 4

筛算法将是更好的执行。我能确定小于4分钟，所有的INT范围的32位的素数（总约105万美元）。当然返回素数的列表不同的东西作为存储器需求会有稍微超过400 MB（1个INT = 4个字节）。使用循环数分别为打印到文件，然后导入到数据库的更多的乐趣:)不过，对于64位的素数，则该程序需要一些修改，也许需要一个分布式执行在多个节点上。还参考下面的链接

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

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