問題タブ [factorization]

指定された値の平方根を 10^100 まで計算するプログラムを Java で作成しています。このためには、BigInteger を使用する必要があることはわかっていますが、扱っているプロセスはあまり効率的ではなく、多くの時間がかかります。プログラムを扱うために数を素因数分解する最速のプロセスは何ですか? より高速なアルゴリズムは何ですか?

前もって感謝します。

ルールに従わなかったことに怒りを覚える前に、検索機能を利用して、この正確な問題に複数のスレッドがあることを確認しました。しかし、私の特定の質問には誰も答えませんでした。

オイラー問題 #3 に取り組んでいます。この問題では、最大の素因数 600851475143 を見つける必要があります。問題を解決するのに助けは必要ありません。私はそれを解決するためのブルートフォース法を作成しました（もっと良いかもしれません）。

プログラムは、小さい数字 (7 桁以下) で行ったすべてのテストで正しく返されます。ただし、長い入力として 600851475143 を入力すると、プログラムから返されることはありません。私の番号は単に大きすぎて入力できませんか? これが起こる原因は何ですか？当初は long ではなく int タグを使用していたためだと思っていましたが、それらを変更しても結果は変わりませんでした。

これは単純なことで、見逃していると確信していますが、何が起こっているのか非常に興味があります。前もって感謝します ：）

Python ライブラリNim​​faを使用して、非常に大きな行列を因数分解しようとしています。マトリックスが非常に大きいため、メモリ内で dence 形式でインスタンス化できないため、代わりにscipy.sparse.csr_matrixを使用します。

ライブラリにはSnmf: Sparse Nonnegative Matrix Factorization (SNMF)と呼ばれる疎行列関数があり、これは私が探しているもののようです。

試してみたところ、因数分解に深刻なパフォーマンスの問題がありました (メモリ表現ではなく速度でした)。スパースな単純な 10 x 95 行列をまだ因数分解できませんでした。

これは、テスト マトリックスを作成する方法です。

そして、これが私がそれを実行する方法です

これでは全然終わりそうにありません。しかし、 m1.todense() を実行すると、数秒で終了します。実際の行列をインスタンス化できないため、これは私にとって良い解決策ではありません。

別の scipy.sparse マトリックス形式を試しましたが、役に立たなかった: csc_matrix、csr_matrix、dok_matrix。

間違ったマトリックス形式を使用していますか? snmf アルゴリズムが迅速に実行するために必要な行列演算は何ですか? 私が見落としている他の間違いはありますか？

私は数学の問題を調べていました: 大きな数の因数を見つけることです. 私は「素因数分解」の方法にたどり着きました。それはすべてphpでコード化するのにうまくいきました。しかし、196 という数の約数 (1、2、4、7、14、28、49、98、196) を知りたいとすると、この数の素因数分解は次のようになることがわかりました ( 2^2)(7^2)。

要因を見つけるには、2 つの要素の間で考えられるすべての組み合わせを作成し、それらを複数回実行する必要があります。

これは私が立ち往生しているところです。これらの項目の組み合わせを作成する関数を見つける必要があります (指数は、その数値の素因数分解よりも高くない場合があります)。この関数は、N 個の要素 (N は 0 より大きく 100 より小さい数値) で機能する必要があります。

私の問題を理解し、それを解決する方法についていくつかのアイデアを持っていることを願っています!

だから私は今Javaコードに取り組んでいます。私はそれを完全にうまく機能させましたが、割り当てのポイントは、大きな数 (30 桁以上) を因数分解することです。それを行いますが、それを行うのに 15 分以上かかる場合があり、これは良くありません。私の教授は、私が使用しているアルゴリズムは 2^70 までの数値に対して機能し、約 5 分で処理できるはずだと保証してくれました。私はそれを行う方法を考え出そうとしています（1ではなく2ずつ増やすなど）が、いくつかの要因をスキップせずにそれをより速く動かす方法を実際に理解できないようです. 何か案は？私も楕円曲線法の方がいいと思っていたのですが、今は取り扱わないようにとのことでした。

これが私のコードです（ps、sqrtは私自身の関数ですが、動作していると確信しています）：

単純な数学を Linq に変換しようとしています。

複数の数の素因数を 1 つのコレクションにまとめたいと考えています。次の整数を考えてみましょう。

8 と 12 の両方で割り切れる最小の数は 24 なので、結果のグループに含めたい

使用した場合Concatの結果は {2,2,2,2,2,3} - 不正解 使用した場合Unionの結果は {2,3} - 不正解

アイテムの最大出現回数を維持する必要があることを認識する組み込みの Linq Set Manipulation 関数がありますか (つまり、満たすのに十分な数が既に存在する場合は別のアイテムを追加しないでください & 存在しない場合は別のものを追加します)

特定の数の因数の特定の製品を見つけるなど、数学の問題を解決しようとするたびに、Pythonでこれを行います

これは非常に簡単で、この例では仕事をすばやく完了できますが、これを書くためのより簡単または単純な方法を知っているかどうか疑問に思っていました. 反復にそれほど多くを使用したり、ほぼ同じコードを何度も繰り返したりせずにこれを行う方法に関するアイデア。これらは明らかに 3 つの要因によるものですが、追加する要因が増えるほど、コードはより長く、より反復的になります。この単純なタイプの問題のコードを単純化する方法についてのアイデアはありますか? ありがとう

数値を素因数分解するプログラムをコーディングしています。プログラムは次のように動作します。

1) 因数分解する数値を入力します (これを「inputNumber」と呼びます)

2) inputNumber を 2、3、5、および 7 (最初の 4 つの素数) で割り切れるかどうかをテストします。これらのいずれかで割れる場合は、できる限り何度でも割ることができます (つまり、12 を 2 で 2 割ると、余りは 3 になります )。配列リスト内の番号と、さらなるテストのために残りを保持します

3) while ループで i=11 (次の素数) から始めて、次のことを行います。

このように、while ループの反復が成功するたびに、剰余が 1、3、7、9 で終わる数で除算されます。すでに 2 で除算されているため、偶数をテストする必要はありません。また、すでに 5 で除算されているため、5 で終わる数をテストする必要もありません。

これは非常に巧妙なアルゴリズムです。なぜなら、1 つの数値を次々にテストして数値を因数分解するよりもはるかに高速だからです。実際、すべての数値の 40% をテストするだけで済みます。

私の質問は次のとおりです。84738329279 を因数分解しようとしたとき、ランダムに選択された数字で、リストの最後の素因数を省略しています。これを理解することはできません。表示される要因は 41、61、および 61 だけです。誰かが私が間違っていることを見つけるのを手伝ってくれますか? ここに私のコードがあります:

前もって感謝します。