我已经看到了几个与此相关的问题,但我想验证我是否遇到了类似的问题。我的代码分配了一个包含大量元素的 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
如果我删除 nothrot
指令来更改此行:
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++ 的细微差别,这将允许我分配这样的数组(即使它绝对很大并且我理解这一点)。我也尝试尽可能多地调试这个问题,但是如果我应该提供其他任何内容,请告诉我,以便我下次遇到麻烦时可以使用这些工具。
最佳答案
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
。
关于c++ - 如何分配当前在分配期间引发 std::bad_alloc 错误的大型 bool 数组?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11093571/