2

我已经看到了几个与此相关的问题，但我想验证我是否遇到了类似的问题。我的代码分配了一个包含大量元素的布尔数组。这是我的代码，在 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'

我认为这意味着分配失败，大概是因为大小（基于类似的问题和其他引用的链接。

CodeBlocks 中的调试器显示即使在它应该被分配之后primes仍然设置为。0x0Valgrind 证实了这一点：

==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++ 的细微差别，这将允许我分配这样的数组（即使它绝对庞大，我理解这一点）。我也尝试尽可能多地调试这个问题，但是如果我应该提供其他任何东西，请告诉我，以便我下次遇到麻烦时可以使用这些工具。

4

3 回答 3

2

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。

于 2012-06-19T03:01:42.307 回答
1

考虑到数据密度和快速操作，使用std::vector<bool>或std::bitset专门为此目的而设计。在一个常规的布尔数组中，每个元素至少分配一个字节，而不是一个位。

于 2012-06-19T02:28:20.483 回答
0

Assuming that 600851475143 is a composite number, its largest prime factor is less than or equal to sqrt(600851475143) or about 775146. Your sieve doesn't need to be any larger than that.

This problem (Project Euler #3) can also be solved with simple brute-forced factorization. That method only takes about .002 seconds on my desktop PC.

于 2012-06-19T02:54:03.850 回答