問題タブ [factorization]

与えられた数の因子を見つけるアルゴリズムを開発しました。したがって、与えられた数が素数であるかどうかを見つけるのにも役立ちます。これが因子や素数を見つけるための最速のアルゴリズムだと思います。

このアルゴリズムは、与えられた数が5 * Nの時間枠で素数であるかどうかを検出します（ここで、Nは入力数です）。したがって、これを線形時間アルゴリズムと呼べることを願っています。

これが利用可能な最速のアルゴリズムであるかどうかを確認するにはどうすればよいですか？誰かがこの問題で助けることができますか？（GNFSやその他の既知のものよりも高速です）

アルゴリズムを以下に示します

あなたのコメントを提供してください..詳細については私に連絡することを躊躇しないでください。

ありがとう、ハリッシュ http://randomoneness.blogspot.com/2011/09/algorithm-to-find-factors-or-primes-in.html

だから私は単に与えられた数のすべての除数を見つけたいのです（数自体を除いて）。現在、私はこれを持っています：

ここで、primesは素数のリストです（正しく、十分に大きいと仮定します）。このアルゴリズムは、すべての素因数を検出するという意味で機能しますが、すべての素因数を検出するわけではありません（つまり、34534を指定すると、{1,2,17267,31,1114}を返しますが、62は組み合わせであるため、{62、557}を見逃します。したがって、557も見逃します。

また、数の素因数を取得しようとしましたが、それをすべての正しい組み合わせのリストに変換する方法がわかりません。

そのアルゴリズムのコードは次のとおりです。

最初のものを修正する方法、または2番目のものから組み合わせのリストを作成する方法についてのアイデアはありますか（私はそれがより速いのでそれを好むでしょう）？

重複の可能性：
数値のすべての除数を効率的に見つける

これは、一般的な「それを行う方法を見つける」よりもはるかに効率の問題ですが、いくつかの奇妙な結果を得た後、誰かが最後の方法がそれほど非効率的である理由を教えてくれるかどうかを確認したいと思います。

方法1：ブルートフォース、最適化なし

方法2：以前と同じですが、今回はプライムが最初かどうかを確認します（これらの場合は最も時間がかかるため、プライムチェックにミラーラビンを使用します）

素因数を見つけるたびに動作する数を減らし、素数のみを試したため、これまでで最も速い方法であると考えられたのは方法3でした（これらは実行時にふるいによって生成され、約34かかりますすべての素数を100万未満にするためのミリ秒）この方法で最後にやらなければならなかったのは、素因数とその力を取り、すべての素数のリストを作成することでした。

方法3：

最初の百万の数を因数分解するのにかかった時間：方法1：7223ミリ秒方法2：8985ミリ秒（素数チェックは私が推測する小さな数には価値がない）方法3：49423ミリ秒

だから私の質問は2つあります：1）なぜ方法3はとても遅いのですか？2）それをより速くすることができる何かがありますか？余談ですが、素数はリストとして計算され、配列に変換されました。そうすればもっと速くなると思いました。悪い動き？

編集：

@yoda と @morispaa に感謝します。あなたはどちらも正しく、@morispaaのソリューションは機能します。つまり、 Zがまたがる空間に関する仮定に基づく変換された係数の私の処理、およびZベクトルの順序と「方向」は、更新すると正しい結果をレンダリングしますRの対角要素が正の要素を持つように、 Qの列の符号を変更します。

私が取り組んでいる変換の詳細については、こちらをお読みください。以下のZ = サンプリングされたゼルニケ多項式。これは、離散ケース (私たちのケース) で直交または完全ではないことが知られています。

@morispaa によって提案されたソリューションが機能する理由についての直感。それについてあなたの意見を聞きたいです：

私の直感では、Rの実数の非負の対角線を何らかの形で適用すると、基底QがZのベクトルと「一致する」ようになり(前に述べたように、ユニタリではありません)、したがって以下のオプション 1 と 2 が得られるということです。それらは異なる変換を表していますが、出力係数はおそらく同様の空間にあります。

より具体的には、Zは「ほぼ」ユニタリであり、これによりQR分解がZに十分近い基底を返すようになるのではないでしょうか? そうして初めて、 Zのベクトルの詳細に関する仮定に基づく変換された係数の処理が、 Qの対角が完全に正の場合は機能するが、負のエントリがある場合は機能しないと想像できます。どう思いますか？

バックグラウンド

MATLAB R2011aとR2010bの両方がマシンにインストールされています。

R2010bからR2011aへの変更の 1 つは、の実装に影響しますqr()(この特定の変更に関するリリース ノートはこちらを参照してください)。

qr()私のプロジェクトが直接および逆変換の直交基底を推定するために使用するものの重要な部分。私のコードは、この変換を入力信号に適用し、変換された係数を処理して、処理された信号を返します。つまり、R2011aで行われた変更によりqr()、この変換の係数を処理するブロックが機能しなくなります (逆変換は、処理された信号の期待される逆変換を返しません)。

どういうわけか、現在返されているQマトリックスはqr()、変換された係数の処理が適切に機能しないという点で、古いバージョンとは異なります。

最初の質問

以上のことから、 R2010bからR2011aを使用するように指示することは可能ですか?qr()

2 番目の質問

QとQ'を使用して、直接変換と逆変換を計算します。詳細はこちらでご覧いただけます。より具体的には、y = Q * xとx = Q' * yを使用して、それぞれ直接変換と逆変換を計算します。直接変換を計算する別の方法は、最小二乗法を使用することです。つまり、次の 2 つのオプションがあります。

オプション 1: QR 因数分解を使用した直接および逆変換:

オプション 2: 最小二乗フィッティングによる直接変換と逆変換

変数は次のとおりです。

R2011a では、上記のオプション 1が機能しなくなりました ( R2010bでは機能します)。直接変換と逆変換に使用するというアイデアが本当に気に入っていqr()ます (すべての新しいベクトルの最小二乗を計算するよりもはるかに高速です)。私のプロジェクトに新しいものを使用したい場合、私の変換を新しいQqr()で再び機能させる方法を知っている人はいますか?

私は計算の複雑さ、BigOh 記法などの研究を始めており、整数因数分解アルゴリズムを実行してその複雑さを判断する任務を負っていました。アルゴリズムを作成して動作していますが、複雑さの計算に問題があります。擬似コードは次のとおりです。

私がやろうとしたことは、非常に間違っていると思います。

f(x) = n-1 + n-1 + 1 + 1 = 2n

それで

f(n) = O(n)

因数分解アルゴリズムは計算が難しいと考えられており、多項式にすることさえできないため、これは間違っていると思います。それで、あなたは私を助けるために何を提案しますか? 多分私は夜のこの時間に疲れすぎて、これをすべて台無しにしています:(

前もって感謝します。

この実装は、CLRS第2版（ページ番号894）から派生しています。while(1)私には疑わしいようです。whileループの終了条件はどうあるべきですか？

試しk<=nましたが、うまくいかないようです。セグメンテーション違反が発生します。コードの欠陥とその修正方法は何ですか？

数値の素因数を取得できますが、コードでは、

数値が 21 だとすると、配列の範囲が 5 であると判断したため、1,3,7,0,0 を取得します。どうすれば 0 を削除して、1,3,7 にすることができますか?

私の通常の検索foo​​は私を失敗させています。整数のすべての因子を返すR関数を見つけようとしています。関数を含むパッケージは少なくとも2つありますfactorize()。gmpとconf.designですが、これらの関数は素因数のみを返します。すべての要素を返す関数が欲しいのですが。

Rには、検索に多くのノイズを加えるファクターと呼ばれる構造があるため、明らかにこれを検索することは困難です。

ある整数 n の因子として存在する最大の階乗数を見つけるアルゴリズムの設計に取り組んでいます。この問題は RGDormey の「コンピュータで解決する方法」に記載されています。アルゴリズムの設計方法について教えてください..答えは整数nの因数であり、階乗数でなければなりません..

私が考えた解決策：

最初に整数が素数でないことを確認してください。プライムの場合、それ以上の解決策はありません..

素数でない場合、整数の最大因数を見つけます

階乗数かどうかを調べます..

はいの場合、それが答えです

そうでない場合は、整数の 2 番目に大きい因数を見つけます。

階乗であるかどうかを確認します...

等々..

Python（2.7）で数値のすべての要素を見つける効率的な方法を誰かが私に説明できますか？

これを行うためのアルゴリズムを作成することはできますが、コーディングが不十分で、多数の結果を生成するには時間がかかりすぎると思います。