問題タブ [factorization]

mxn 行列 A から始めて、それを 2 つの行列 mxr と rxn に因数分解します。r は行列 A の次元より大きくてもかまいません。

nnmf は、r< min(size(A))

行列を 2 つの行列に因数分解する方法はありますか?

私は、Interview Street の「UnFriendly Numbers」パズルに取り組んでいます。

こんなふうになります：

与えられた整数と別の整数のリストから、与えられた整数にのみ固有であり、他の整数のリストと共有されていない係数を見つけます。

したがって、セット 1 (セット Y) が (および n が指定された数値である) 場合:

∃Y{z|n % z = 0}

基本的に: すべての z に Y があり、z は n % z が 0 の数値です。

Y の集合差から、他の数のリストのすべての因数を含む集合を差し引いたものが必要です。

では、これにどのようにアプローチしますか？

整数 n の因数を見つけますか? 他の数値のすべての要因と、一意ではない要因を除外するだけですか?

それとも、n の因数だけを見つけて、それらを使用して他の数を割り、一意でない数を除外しますか?

それとも素因数分解せずにやる方法ありますか？

ここまでは、試行分割、ポラードのロー、ブレントのポラードのローのバリエーション、フェルマーの因数分解法を使用してきました。Lucas-Lehmer primality test と Euclids GCD も利用しました。

しかし、これまでのところ、間違った答えの組み合わせまたは制限時間を超えているだけです。既知の解決策には、ホイール プライム シーブが関係していると思われますが、それが何であるかはわかりません。

とにかく、ありがとう。

Spring MVCを使用しorg.springframework.ui.Modelて、コントローラー内のメソッドパラメーターで指定する必要がないように、を因数分解する方法はありますか？

言い換えれば、私は現在このようにそれをやっています：

そして、私はそのようにしたいと思います：

ただし、URLを呼び出すと、例外がスローされます。

を使用したときに同じエラーが発生しましたorg.springframework.ui.ModelMap。

天才的な解決策はありますか？

助けてくれてありがとう:)

与えられた数n（n = p ^ a * q ^ b、いくつかの素数p、qおよびいくつかの整数a、b）および与えられた数φ（n）（http：//en.wikipedia。 org / wiki / Euler％27s_totient_function）p、q、aおよびbを検索します。

キャッチは、nとφ（n）が約200桁であるため、アルゴリズムは非常に高速である必要があるということです。非常に難しい問題のようで、φ（n）の使い方がまったくわかりません。

これにアプローチする方法は？

楽しみのために、私はC ++でいくつかの数学を実装し、フェルマーの素因数分解法を実装しようとしましたが、それが何を返すのか理解していないのです。私が持っているこの実装は105、ウィキペディアの記事に記載されている例番号5959を返します。

ウィキペディアの擬似コードは次のようになります。

それが正方形であることを期待して、aのさまざまな値を試します。

私のC++実装は、次のようになります。

何が返ってくるの？戻ってきたばかりのようですが、これは？a + bの要因ではありません。5959

編集

ポラード ロー因数分解法を使用して数値を因数分解するたびに、ポラード ロー因数分解の前にその素数をチェックする必要がありますか? はいの場合、任意の数を因数分解するたびに、Miller Rabin の素数性テストまたは任意の素数性テストを実装する必要がありますが、強力な疑似素数を処理する必要があります。複雑ではありませんか? これを処理する簡単で高速な方法はありますか? (私はこれらのテストを 10 桁までの数字に使用しています)

ポラードローの実装を手伝ってくれる人はいますか？これをCで実装しました。10桁までの数値では正常に機能しますが、それ以上の数値を処理することはできません。

18桁までの数の因数分解を実行するためにそれを改善するために私を助けてください。私のコードはこれです：

長いコードでごめんなさい.....私は新しいコーダーです。

私はPythonの経験がありません。チュートリアルの資料をいくつか見ましたが、高度なコードを理解するのは難しそうです。だから私はより具体的な答えを求めてここに来ました。私にとっての使命は、コンピューターのコードをやり直すことです。

シナリオは次のとおりです。

私は関係学習でテンソル因数分解を研究している大学院生です。次のように、このアルゴリズムを実行するためのコードを提供する論文[1]:

こんなに長いコードを貼り付けるのは退屈ですが、問題を解決する方法は他にありません。申し訳ありません。

このモジュールをインポートし、作成者のWeb サイトに従って引数を渡します。

データセット us-presidents.rdf はこちらにあります。

私の質問は次のとおりです。

1. コードノートによると、テンソル X はリストです。私はこれをよく理解していません.Pythonでリストをテンソルに関連付けるにはどうすればよいですか? Python の tensor = list を理解できますか?
2. 最初に RDF 形式をトリプル (主語、述語、目的語) 形式に変換する必要がありますか? X のデータ構造がよくわかりません。手動で X に値を代入するにはどうすればよいですか?
3. 次に、それを実行する方法は？

作者の許可なく作者のコードを貼り付けますが、それは侵害行為ですか? もしそうなら、申し訳ありませんが、すぐに削除します。

問題は少し退屈かもしれませんが、これらは私にとって重要です。どんな助けでも大歓迎です。

[1] Maximilian Nickel, Volker Tresp, Hans-Peter Kriegel, A Three-Way Model for Collective Learning on Multi-Relational Data, in Proceedings of the 28th International Conference on Machine Learning, 2011 , Bellevue, WA, USA

このfactorコマンドは、指定された整数 NUMBER の素因数を出力します。

やってみたところ

そのような大きな数であっても、ミル内で結果が得られます。

どのアルゴリズムを使用していますか?

因数分解を実装する方法については多くの質問がありますが、本番環境で使用する場合は、オープン ソース ライブラリを使用して、効率的で十分にテストされたものをすぐに取得したいと考えています。私が探している方法は次のようになります。

n=12 の場合、{2,2,3} を返します。

ライブラリには、long 型または BigInteger 型を処理するためのオーバーロードもある場合があります。

問題は特定のアプリケーションに関するものではなく、この問題を適切に処理するライブラリを持つことです。多くの人は、数値の範囲に応じて異なる実装が必要であると主張していますが、この点に関しては、ライブラリが実行時に最も合理的な方法を選択することを期待しています。

効率的とは、「世界最速」という意味ではありません (そのための JVM では作業しません...)。int と long range を 1 時間ではなく 1 秒以内に処理することを意味します。