'a'と 'b'の値を見つけるための最適なアルゴリズムを設計する
surajs1n
合成数（n > 3）が与えられ、次のように書くことができると仮定しn = a*bます。ここで、aとbは任意の整数です。
今、私たちの仕事は、の値を計算することである＆Bを関数があるよう、最小限に抑えます。。f(a,b) = |a-b|
以下に示すアプローチを実装しました。
int n;
cin >> n; // Take it from the user
/* Now, find the value of the a and b */
int a = 1;
int b = n;
int temp_a;
int temp_b;
for(temp_a=1; temp_a<=sqrt(n); temp_a++) {
if(n % temp_a == 0) {
temp_b = n / temp_a;
if((temp_b - temp_a) < (b - a)) {
b = temp_b;
a = temp_a;
}
}
}
print a and b
しかし
、可能であれば、それをそれ以上に減らしたい。
stgatilov
sqrt（N）以下のNの最大除数を見つけたいとします。これを行う最も簡単な方法は、考えられるすべての除数を反復処理してチェックすることです。最悪の場合、O（sqrt（N））時間がかかります。
残念ながら、最悪の場合、O（log N）時間でこの問題を解決する方法はありません。実際、どのpについてもO（（log N）^ p）時間でもそれを行うことはできません。可能であれば、バイト単位のサイズの多項式時間で任意の数の素因数分解を見つけることができることを示すのは簡単です。現在、誰もそれを行うことはできません。また、広く使用されているRSA暗号システムがあります。これは、数値をそれほど速く因数分解できないという事実に強く依存しています。それが、誰もが量子コンピューターをとても恐れている理由の1つです=）
ただし、O（sqrt（N））よりも漸近的に高速なアルゴリズムがあります。また、因数分解のためのより高速なヒューリスティックアルゴリズムがいくつかあります。この問題に関するウィキペディアの記事を読むことを強くお勧めします。
複雑さをわずかに改善する方法の1つは、sqrt（N）までのすべての素数を事前計算することです。あなたが分割しようとする場合は、Nをそれらだけで、あなたはの素因数分解を見つけることができるだろうNを。素因数分解がわかっているので、再帰検索を使用して、考えられるすべての除数を効率的に反復できます。階乗の検索には、チェックされている素数と同じくらいの時間がかかります。つまり、O（sqrt（N）/ log（N））です。すべての除数を反復処理するには、それらの約数の数に比例する時間がかかります。これは、Nのどの多項式よりも漸近的に短くなります。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
編集
関連記事
Related 関連記事
- 1
アルゴリズムは、XOR X = B + Xのための解決策を見つけること
- 2
ユージンマイヤーズの差分アルゴリズム：「A」と「B」の最長共通部分列を見つける
- 3
乗数と除数の値を計算するための最適化アルゴリズム
- 4
f（x）= a * min（b、x）？の形式の関数の最大値を見つけるためのアルゴリズム
- 5
最大値と最小値を見つけるためのJavaアルゴリズムの助けが必要
- 6
グラフ重心を見つけるための効率的なアルゴリズムとは何ですか？
- 7
x ^ n <= yとなるような最大のnを見つけるための最速のアルゴリズム
- 8
A ^ 5 + B ^ 5 + C ^ 5のすべての可能な値を見つけるアルゴリズム？
- 9
2つの画像を比較するときに異なる領域のエッジを見つけるためのアルゴリズムまたはツール
- 10
製品を注文するときに最良の価格の組み合わせを見つけるためのアルゴリズム
- 11
アルゴリズム：2つの配列を「Aのみ」、「AとBの交差」、「Bのみ」に分割します。
- 12
与えられた内積と別のリストを見つけるためのアルゴリズム
- 13
加重2Dマトリックスの指定されたソースと宛先の場所の間の最適なパスを見つけるために、フラッディングアルゴスリムを適用する方法
- 14
数値最適化の質問-製品とシナリオのどちらかを選択するために必要なアルゴリズム
- 15
グループと優先グループを持つオブジェクトの最適な割り当てを見つけるためのアルゴリズム
- 16
大きなaとbの（a * b）％mを見つける方法は？
- 17
アルゴリズムは、人と人との取引の最小数を見つけるために
- 18
ダブルスとサブセットを持つサブセットを見つけるための効率的なアルゴリズムは一緒です
- 19
大きなデータフレームのrの係数で変数の最小値と最大値を見つけるための計算上非課金アルゴリズム？
- 20
なぜ、アルゴリズムの時間計算量を見つける際に、対数の基数が常に2と見なされるのですか？
- 21
ベースとパワーの両方がバイナリであるバイナリ値のパワーを見つけるための最良のアルゴリズム方法は何ですか？
- 22
aとbの間のすべての数の合計を見つける：Ruby
- 23
a <b <cおよびv [a] <v [c] <v [b]であるような配列内の3つの数値を見つけるアルゴリズム。
- 24
有向グラフのルート頂点を見つける（または存在しないことを報告する）O（| V | + | E |）時間アルゴリズムを設計します
- 25
2つの同一線上のセグメントと重複するセグメントを見つけるためのアルゴリズム
- 26
アルゴリズムの設計-値を追跡するために辞書とリストを使用する場合
- 27
最小全域木を見つけるための欲張りアルゴリズムが確実に停止することを証明する
- 28
グーグルマップがパスを見つけるために使用する検索アルゴリズムとその理由は何ですか？
- 29
タプルのセット（値、コスト）を与えると、指定された数を格納するためのコストが最小のタプルの組み合わせを見つけるアルゴリズムはありますか？
コメントを追加