c++ - 多数の取り扱い

Question

これは、Project Euler サイトの問題 3です。

私は解決策を求めているわけではありませんが、おそらく私のアプローチが何であるかを知っていると思います. 私の質問に対して、 unsigned int を超える数値をどのように処理しますか?

これに対する数学的アプローチはありますか?もしそうなら、どこでそれについて読むことができますか?

score 5 · Accepted Answer

あなたは試しましたunsigned long longか、それとももっと良い/具体的にuint64_tは？

uint64_t[2 ⁶⁴ -1] [64 ビット整数、符号なし]の範囲より大きい数値を処理したい場合は、bignum を調べる必要があります: http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic。

600,851,475,143 は質問によって与えられた数であり、2 ⁶⁴ -1 は 18,446,744,073,709,551,615 に等しくなります。それは間違いなく十分な大きさです。

score 4 · Accepted Answer

最近素因数分解を知っている子供に教えたところ、素数のリストがあればアルゴリズムは自明です。

2 から始めて、それを目標にできる限り何度でも分割し、剰余をゼロにします。
次の素数 (3) を取り、それをステップ 1 のようにターゲットに分割します
見つけた各要因を書き留め、残りがなくなるまで繰り返します。

リクエストごとに、アルゴリズムの疑似コードを追加しました:

def factor(n):
    """returns a list of the prime factors of n"""
    factors = []
    p = primes.generator()
    while n > 1:
        x = p.next()
        while n % x == 0:
            n = n / x
            factors.append(x)
    return factors

を連続して呼び出すとp.next()、一連の素数 {2, 3, 5, 7, 11, ...} の次の値が得られます。その疑似コードが実際に動作する Python コードに似ているのは、まったくの偶然です。primes.generator()の定義が 1 行短い (ただし、1 行の長さは 50 文字です)ことは、おそらく言うべきではありません。_{GNU プログラムは log 2} ( n ) >= 40のfactor入力を受け入れないため、私が最初にこの「コード」を書きました。

score 0 · Accepted Answer

Windows では、コンパイラが 64 ビット整数をサポートしていない場合、LARGE_INTEGERとULARGE_INTEGERを使用できます。

score 0 · Accepted Answer

0

使用する

long long

GCCで

と

__int64

VCで

于 2010-05-23T06:09:52.043 に答える

score 0 · Accepted Answer

使用する

long long

これは、GCC と新しいバージョンの Visual Studio (2008 以降と思われます) の両方でサポートされています。

score 0 · Accepted Answer

おそらく、問題を処理する最も簡単な方法は、Python を使用することです。Python バージョン > 2.5 では、組み込みの長精度算術演算がサポートされています。精度は、コンピューターのメモリにのみ依存します。詳細については、このリンクを参照してください。

score 0 · Accepted Answer

long longその問題のためにそれを行います。を超える他の Project Euler の問題についてlong longは、おそらくlibgmp (特にそのC++ ラッパークラス) を使用します。

c++ - 多数の取り扱い

7 に答える 7

リクエストごとに、アルゴリズムの疑似コードを追加しました:

Related

Reference