2

これに関連するいくつかの質問を見てきましたが、同様の問題が発生していることを確認したいと思います。私のコードは、非常に多くの要素を持つブール配列を割り当てます。これは私のコードで、x86_64Linuxマシンでコンパイルしています。

#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設定されたままであることを示して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 ++のニュアンスが欠けているかどうかを知りたいです（それは絶対に巨大であり、私はそれを理解していますが）。私もこの質問を可能な限りデバッグしようとしましたが、他に何か提供すべきことがあれば、次に問題が発生したときにツールを使用できるように知らせてください。

4

3 に答える 3

2

使用している（大きな）数を因数分解するために使用できる非常に単純なアルゴリズムは、ポラードのローアルゴリズムです。

簡潔にするために数学的な説明は省略しますが、詳細については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::bitsetboolの通常の配列では、すべての要素にビットではなく少なくとも1バイトが割り当てられます。

于 2012-06-19T02:28:20.483 に答える
0

それが合成数であると仮定すると600851475143、その最大の素因数は以下sqrt(600851475143)です775146。ふるいはそれより大きくする必要はありません。

この問題（プロジェクトオイラー＃3）は、単純なブルートフォース分解でも解決できます。この方法は、デスクトップPCでは約0.002秒しかかかりません。

于 2012-06-19T02:54:03.850 に答える