如何分配一個當前在分配過程中拋出std :: bad_alloc錯誤的大量布爾數組？

Question

我已經看到了幾個與此相關的問題，但我想驗證我是否有類似的問題。我的代碼分配一個具有非常大量元素的布爾數組。這是我的代碼，編譯一個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中對其進行了原型設計，並正確返回了6857的最大素數因子。

Answer 2

使用std::vector<bool>或std::bitset這是專門爲此目的而設計的數據密度和快速操作的想法。在布爾的常規數組中，每個單元至少分配一個字節，而不是一個字節。

Answer 3

假設600851475143是一個合數，它的最大素因子小於或等於sqrt(600851475143)或大約775146。您的濾網不需要比這更大。

這個問題（歐拉項目＃3）也可以通過簡單的強制分解來解決。這種方法在我的臺式電腦上只需要0.002秒。