c++ - 如何分配当前在分配期间抛出 std::bad_alloc 错误的大量 bool 数组？

Question

我已经看到几个与此相关的问题，但我想验证我是否遇到了类似的问题。我的代码分配了一个包含大量元素的 bool 数组。这是我的代码，在 x86_64 Linux 机器上编译:

#include <iostream>
#include <math.h>

using std::cout;
using std::endl;
using std::nothrow;

long problem3()
{
    long upper_bound = 600851475143;
    long max_prime_factor = 1;
    long max_possible_prime = (long) sqrt(upper_bound) + 1;
    bool * primes;
    primes = new (nothrow) bool[upper_bound];
    primes[0] = false; //segmentation fault occurs here
    primes[1] = false;
    for (long i = 2; i < upper_bound; i++)
       primes[i] = true;
    for (long number = 2; number < max_possible_prime; number++)
    {
        if (primes[number] == true)
        {
            if (upper_bound % number == 0)
            {
                max_prime_factor = number;
            }
            for (long j = number + number; j < upper_bound; j += number)
                primes[j] = false;
        }
        else { continue; }
    }
    return max_prime_factor;
}

int main ( int argc, char *argv[] )
{
    cout<<"Problem 3: "<<problem3()<<endl;
}

构建此代码并按原样运行它会在此行出现段错误:

primes[0] = false

如果我删除 nothrow 指令来更改此行:

primes = new (nothrow) bool[upper_bound];

为此:

primes = new bool[upper_bound];

我收到一条错误消息，指出:

terminate called after throwing an instance of 'std::bad_alloc'

我认为这意味着分配失败，大概是因为大小(基于 similar questions 和 other referenced links 。

CodeBlocks 中的调试器显示 primes 仍然设置为 0x0，即使在它应该被分配之后也是如此。 Valgrind 证实了这一点:

==15436== Command: ./main
==15436== 
==15436== Invalid write of size 1
==15436==    at 0x400A81: problem3() (main.cpp:54)
==15436==    by 0x400B59: main (main.cpp:77)
==15436==  Address 0x0 is not stack'd, malloc'd or (recently) free'd
==15436== 
==15436== 
==15436== Process terminating with default action of signal 11 (SIGSEGV)
==15436==  Access not within mapped region at address 0x0
==15436==    at 0x400A81: problem3() (main.cpp:54)
==15436==    by 0x400B59: main (main.cpp:77)
==15436==  If you believe this happened as a result of a stack
==15436==  overflow in your program's main thread (unlikely but
==15436==  possible), you can try to increase the size of the
==15436==  main thread stack using the --main-stacksize= flag.
==15436==  The main thread stack size used in this run was 8388608.
==15436== 
==15436== HEAP SUMMARY:
==15436==     in use at exit: 0 bytes in 0 blocks
==15436==   total heap usage: 1 allocs, 0 frees, 0 bytes allocated
==15436== 
==15436== All heap blocks were freed -- no leaks are possible
==15436== 
==15436== For counts of detected and suppressed errors, rerun with: -v
==15436== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 3 from 3)
Segmentation fault 

问题:我知道 std::vector，那么我应该用它来分配这个数组吗？我也愿意尝试不同的算法，但我想知道我是否遗漏了 C++ 的细微差别，这将允许我分配这样一个数组(即使它绝对很大而且我理解)。我也尝试尽可能多地调试这个问题，但如果还有什么我应该提供的，请告诉我，这样我下次遇到麻烦时就可以使用这些工具。

Answer 1

Pollard 的 Rho 算法是一种极其简单的算法，您可以使用它来分解您正在处理的(大)数。

为了简洁起见，我将省略数学解释，但您可以在 Wikipedia 上找到详细信息文章。

unisgned long long GCD(unisgned long long x, unisgned long long y)
{
    while (y != 0)
    {
        unsigned long long t = b;
        b = a % b;
        a = t;
    }

    return a;
}

unsigned long long f(unsigned long long x, unsigned long long n)
{
    return (x * x + 1) % n;
}

unsigned long long PollardRho(unsigned long long n)
{
    unsigned long long x = 2, y = 2, d = 1;

    while (d == 1)
    {
        x = f(x);
        y = f(f(y));
        d = GCD(std::abs(x - y), n);
    }

    if (d == n)
        throw "Failure";
    return d;
}

unsigned long long MaxFactor(unsigned long long n)
{
    unsigned long long largest = 1;

    while (n != 1)
    {
        unsigned long long factor = PollardRho(n);
        largest = std::max(largest, factor);
        n /= factor;
    }

    return largest;
}

注意:我实际上并没有测试 C++ 代码。我在 Mathematica 中对其进行了原型(prototype)设计，它正确地返回了最大质因数 6857。