algorithm - 300 000 000 000 の素因数?

Question

3000億以上の素因数を調べないといけない。それらのリストに追加する機能があります...非常にゆっくりと！現在、約1時間実行されており、静止するにはかなりの距離があると思います。私はそれを完全に間違っていますか、それとも期待されていますか?

編集：番号600851475143の最大の素因数を見つけようとしています.

編集：結果：

{
    List<Int64> ListOfPrimeFactors = new List<Int64>();
    Int64 Number = 600851475143;
    Int64 DividingNumber = 2;

    while (DividingNumber < Number / DividingNumber)
    {
        if (Number % DividingNumber == 0)
        {
            ListOfPrimeFactors.Add(DividingNumber);
            Number = Number/DividingNumber;
        }
        else
            DividingNumber++;
        }
        ListOfPrimeFactors.Add(Number);
        listBox1.DataSource = ListOfPrimeFactors;
    }
}

score 25 · Accepted Answer

因数分解している数を見つけたら、各因数で割ることを覚えていますか?

たとえば、2 が因数であることがわかったとします。それを因数のリストに追加できますが、因数分解しようとしている数をその値で割ります。

今、あなたは 1500 億の因数だけを探しています。毎回、見つけた要因から始めるべきです。したがって、2 が要因である場合は、2 をもう一度テストします。次に見つけた因子が 3 である場合、2 から再度テストしても意味がありません。

等々...

score 20 · Accepted Answer

ブルートフォースを使用して素因数を見つけることは困難です。これは、使用している手法のように聞こえます。

速度を上げるためのいくつかのヒントを次に示します。

高くではなく低く始める
素数であるかどうかを確認するために潜在的な各要素をわざわざテストする必要はありません。素数の可能性が高い数 (1、3、7、または 9 で終わる奇数) をテストするだけです。
わざわざ偶数 (すべて 2 で割り切れる) や 5 で終わるオッズ (すべて 5 で割り切れる) をテストしないでください。もちろん、実際には 2 と 5 を飛ばしてはいけません!!
素因数を見つけたら、必ず割り切ってください。元の膨大な数を使い続けないでください。以下の私の例を参照してください。
要因が見つかった場合は、もう一度テストして、そこに複数回含まれているかどうかを確認してください。あなたの番号は2x2x3x7x7x7x31またはそのようなものかもしれません.
>= sqrt(残りの大きな数)に達したら停止

編集: 簡単な例: 275 の因数を見つけています。

275 が 2 で割り切れるかどうかをテストします。275/2 = int(275/2) ですか? いいえ、失敗しました。
275 が 3 で割り切れるかどうかをテストします。失敗しました。
スキップ4！
275 が 5 で割り切れるかどうかをテストします。はい! 275/5 = 55. したがって、新しいテスト番号は 55 になります。
55が 5 で割り切れるかどうかをテストします。はい! 55/5 = 11. したがって、新しいテスト番号は 11 になります。
しかし、5 > sqrt (11) なので、11 は素数であり、やめることができます!

したがって、275 = 5 * 5 * 11

もっと理にかなっていますか？

score 17 · Accepted Answer

大きな数の因数分解は難しい問題です。実際、私たちは RSA を安全に保つためにこれに頼っています。ただし、ウィキペディアのページを参照して、役立つアルゴリズムへのポインタを確認してください。しかし、その数が少ない場合、どこかで必要のない作業を何度もやり直さない限り、実際にはそれほど長くはかからないはずです.

ブルートフォースソリューションの場合は、いくつかの小さな最適化を行うことができることを覚えておいてください。

特に 2 をチェックしてから、奇数のみをチェックします。
数の平方根までチェックするだけで済みます (それまでに因数が見つからない場合、その数は素数です)。
因数を見つけたら、元の数を使用して次の因数を見つけず、見つかった因数で割り、新しい小さい数を検索します。
因数を見つけたら、それをできるだけ多く分割します。その後、その数値またはそれより小さい数値をもう一度確認する必要はありません。
上記のすべてを実行すると、見つかった新しい因子はそれぞれ素数になります。これは、小さい因子が既に削除されているためです。

score 10 · Accepted Answer

これがXSLTソリューションです！

このXSLT変換には0.109秒かかります。

<xsl:stylesheet version="2.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
 xmlns:xs="http://www.w3.org/2001/XMLSchema"
 xmlns:saxon="http://saxon.sf.net/"
 xmlns:f="http://fxsl.sf.net/"
 exclude-result-prefixes="xs saxon f"
 >
 <xsl:import href="../f/func-Primes.xsl"/>

 <xsl:output method="text"/>


 <xsl:template name="initial" match="/*">
   <xsl:sequence select="f:maxPrimeFactor(600851475143)"/>
 </xsl:template>

 <xsl:function name="f:maxPrimeFactor" as="xs:integer">
   <xsl:param name="pNum" as="xs:integer"/>

   <xsl:sequence select=
    "if(f:isPrime($pNum))
       then $pNum
       else
         for $vEnd in xs:integer(floor(f:sqrt($pNum, 0.1E0))),
             $vDiv1 in (2 to $vEnd)[$pNum mod . = 0][1],
             $vDiv2 in $pNum idiv $vDiv1
           return 
             max((f:maxPrimeFactor($vDiv1),f:maxPrimeFactor($vDiv2)))
    "/>
 </xsl:function>
</xsl:stylesheet>

この変換により、わずか0.109秒で正しい結果（最大素因数600851475143）が生成されます。：

6857

変換では、XSLTの関数型プログラミング用のライブラリでf:sqrt()定義f:isPrime()されたを使用します。それ自体は完全にXSLTで書かれています。FXSL 2.0FXSL

f:isPrime()フェルマーの小定理を使用して、原始性を効率的に決定できるようにします。

score 3 · Accepted Answer

最後に誰も言及していないことをもう 1 つ。因子を見つけて分割するたびに、失敗するまでその因子を試し続けます。

64 には素因数 2 が 1 つしかありません。2 を割り切れなくなるまで割り続ければ、それはかなり簡単にわかります。

score 2 · Accepted Answer

平方根が重要である理由を理解するための鍵は、nの平方根より下の n の各要素には、それより上に対応する要素があることを考慮してください。これを確認するには、x が n の因数である場合、x/n = m を考えます。これは、x/m = n を意味するため、m も因数です。

score 2 · Accepted Answer

$ time factor 300000000000 > /dev/null

real        0m0.027s
user        0m0.000s
sys         0m0.001s

1 時間もかかるとしたら、何か間違ったことをしているということです。どこかに無限ループがあるかもしれません - 32 ビット整数を使用していないことを確認してください。

score 1 · Accepted Answer

これがあなたたちのためのHaskellの良さです:)

primeFactors n = factor n primes
  where factor n (p:ps) | p*p > n = [n]
                        | n `mod` p /= 0 = factor n ps
                        | otherwise = p : factor (n `div` p) (p:ps)
        primes = 2 : filter ((==1) . length . primeFactors) [3,5..]

それらを見つけるのに約0.5秒かかったので、私はそれを成功と呼びます。

score 1 · Accepted Answer

具体的な番号は300425737571？それは131*151 * 673*22567に自明に因数分解されます。私はすべての騒ぎが何であるかわかりません...

score 1 · Accepted Answer

最速のアルゴリズムはふるいアルゴリズムであり、実装とテストが複雑な離散数学の難解な領域に基づいています (少なくとも私の頭の上)。

因数分解の最も単純なアルゴリズムは、おそらく (他の人が言っているように) エラトステネスのふるいです。これを使用して数値を因数分解する際に覚えておくべきことN:

一般的な考え方: 可能な整数因子の増加するシーケンスをチェックしてx、候補数が均等に分割されているかどうかを確認していますN(C/Java/JavascriptN % x == 0では、N が素数ではないかどうかを確認します)。
まで行く必要がありますがsqrt(N)、実際には計算しませんsqrt(N): テスト係数 x がテストに合格する限り、ループしますx*x<N
以前の素数の束を保存するメモリがある場合は、それらのみをテスト要因として使用します（素数 P がテストに失敗した場合は、P*P > N_max二度と使用しないため保存しないでください）
以前の素数を保存しなくても、考えられる要因については、x2 とすべての奇数をチェックしてください。はい、もっと時間がかかりますが、妥当なサイズの数値の場合はそれほど長くはありません。素数カウント関数とその近似により、素数の割合を知ることができます。この割合は非常にゆっくりと減少します。2 ⁶⁴ = 約 1.8x10 ¹⁹の場合でも、おおよそ 43 個の数に 1 個が素数です (= 奇数 21.5 個に 1 個が素数です)。^{2 64}未満の数の因数の場合、それらの因数は 2 ³²x未満です。ここで、約 20 個の数に 1 個が素数です = 奇数の 10 個に 1 個が素数です。したがって、10 倍の数をテストする必要がありますが、ループは少し高速になるはずであり、それらすべての素数を格納するのをいじる必要はありません。

少し複雑ですが、それでもかなり理解しやすい古い単純なふるいアルゴリズムもあります。ディクソン、シャンクス、フェルマーの因数分解アルゴリズムを参照してください。これらのうちの 1 つに関する記事を一度読んだことがありますが、どれがどれだったか思い出せませんが、それらはすべて非常に単純で、2 乗の差の代数的性質を使用しています。

数値が素数であるかどうかをテストしているだけでN、因数自体は気にしない場合は、確率的素数性テストを使用します。Miller-Rabinが最も標準的なものだと思います。

score 1 · Accepted Answer

夢中になったので、これに時間を費やしました。まだここにコードを貼り付けることはしません。興味がある場合は、代わりにこの factor.py Gistを参照してください。

この質問を読む前は、因数分解について何も知りませんでした (まだ知りません)。上記のBradCの回答の単なる Python 実装です。

私の MacBook では、質問に記載されている数値 (600851475143) を因数分解するのに 0.002 秒かかります。

明らかに、これを行うためのはるかに高速な方法が必要です。私のプログラムは、6008514751431331 の因数を計算するのに 19 秒かかります。しかし、Factorisサービスはすぐに答えを吐き出します。

score 1 · Accepted Answer

答えを得ることができる 1 つのサイトがあります: Factoris - オンライン因数分解サービス. 非常に大きな数を処理できますが、代数式も因数分解できます。

score 1 · Accepted Answer

私はそれが非常に長くかかるとはまったく思っていません-それは特に大きな数ではありません.

コードの問題の原因となっている数値の例を教えてください。

score 0 · Accepted Answer

アルゴリズムはFUBARである必要があります。これは、Pythonの1.6GHzネットブックでは約0.1秒しかかかりません。Pythonはその驚異的な速度で知られていません。ただし、任意精度の整数があります。

import math
import operator

def factor(n):
    """Given the number n, to factor yield a it's prime factors.
    factor(1) yields one result: 1. Negative n is not supported."""
    M = math.sqrt(n)  # no factors larger than M
    p = 2             # candidate factor to test
    while p <= M:     # keep looking until pointless
        d, m = divmod(n, p)
        if m == 0:
            yield p   # p is a prime factor
            n = d     # divide n accordingly
            M = math.sqrt(n)  # and adjust M
        else:
            p += 1    # p didn't pan out, try the next candidate
    yield n  # whatever's left in n is a prime factor

def test_factor(n):
    f = factor(n)
    n2 = reduce(operator.mul, f)
    assert n2 == n

def example():
    n = 600851475143
    f = list(factor(n))
    assert reduce(operator.mul, f) == n
    print n, "=", "*".join(str(p) for p in f)

example()

# output:
# 600851475143 = 71*839*1471*6857

（このコードは、指ぬきを埋めるのに十分な数論について私が知らないという事実に反して機能しているようです。）

score 0 · Accepted Answer

エラトステネスのふるいを使用して素数を見つけ、自分の数が見つけたもので割り切れるかどうかを確認できます。

score 0 · Accepted Answer

剰余mod（n）を確認するだけで済みます。ここで、nは素数<= sqrt（N）です。ここで、Nは因数分解しようとしている数値です。非常に遅いコンピュータやTI-85であっても、実際には1時間以上かかることはありません。

score 0 · Accepted Answer

「5で終わらない奇数のみをテストする」提案を少し拡張/改善するために...

3 より大きいすべての素数は、6 の倍数より 1 大きいか 1 小さいかのいずれかです (x の整数値の場合、6x + 1 または 6x - 1)。

score -1 · Accepted Answer

比較的素朴なブルートフォースでも、それほど長くはかからないはずです。その特定の数については、頭の中で約 1 秒で因数分解できます。

あなたは解決策を望んでいないと言いますが（？）、ここにあなたの「微妙な」ヒントがあります。数の唯一の素因数は、最小の 3 つの素数です。

score -1 · Accepted Answer

そのサイズの半素数は暗号化に使用されるため、正確には何に使用したいのか知りたいです。

それはさておき、現在、比較的短い時間で大きな数の素因数分解を見つける良い方法はありません。

algorithm - 300 000 000 000 の素因数?

19 に答える 19

Related

Reference