XおよびYは 100 桁を超える整数です。[ , [Pの範囲内にあり、「最良の」素数分解 (つまり、最もユニークな素因数を持つ分解) を保証する整数を見つけます。XY
私がやったことは、素数をチェックし、範囲内の各数値を分解して、ルールを尊重する数値を見つけることです。これを行う他の方法はありますか？
上記の例では、123456 は に分解されますが
2^6 * 3^1 * 643^1、2 * 2 * 2 * 2 * 2 * 2 * 3 * 643これは 3 つの一意の要素にすぎません。
一方、答え 123690 は 6 つの一意の要素に分解され
2^1 * 3^1 * 5^1 * 7^1 * 19^1 * 31^1ます。
すべての素数のリストを順番に (2,3,5,7...) 取り、数値 >= X になるまでそれらを掛け始めます (2 * 3 * 5 *...)。この数値を P' と呼びます。<= Y の場合、完了です。P = P' です。そうでない場合は、数値 [X,Y] を探して P'/2、P'/3、P'/5 などの計算を開始します。それが見つからず、数値 < X になった場合は、次の素数を P' に乗算して続行してみてください。それでも失敗する場合は、範囲 [X,Y] がかなり小さいため、その範囲内のすべての数値を因数分解する方法に戻ります。
小さな範囲 (YX が小さい) の場合、サイズ Y-X+1 の配列を割り当て、それをゼロにしてから、すべての素数 <= YX について、素数の倍数に対応する配列要素に 1 を追加します (単純なふるい)。次に、合計が最大の要素を検索します。その合計 n が (YX) n >= X である場合、それが答えです。そうでない場合は、テーブル内のいくつかの n に対して p n > Xとなる素数 p に到達するまで、YX より大きい素数のふるい分けを続けます...
範囲の大きさに応じて、上記の2つの方法のいずれかが機能するはずです...
素数の列挙に関する質問への答えは、ふるいを使用して問題を解決する方法を見つけることです。あなたの場合、多数の因数を持つ「反素数」の数を探していますが、原則は引き続き適用されます。
この質問の鍵は、ほとんどの数値について、ほとんどの要因が小さいということです。したがって、私の提案は、すべてゼロに初期化された整数を含む範囲 X から Y のふるいを設定することです。次に、すべての素数をある制限より小さく、便利な大きさであるが、明らかに X よりもはるかに小さいと考えます。素数ごとに、素数の倍数であるふるいの各要素に 1 を追加します。すべての素数をふるいにかけた後、カウントが最大のふるいの場所は、最も明確な素因数を持つ X と Y の間の数に対応します。
例を考えてみましょう: 範囲 100 から 125 を取り、素数 2、3、5、および 7 でふるいにかけます。次のような結果が得られます。
100 2 5
101 (101)
102 2 3 (17)
103 (103)
104 2 (13)
105 3 5 7
106 2 (53)
107 (107)
108 2 3
109 (109)
110 2 5 (11)
111 3 (37)
112 2 7
113 (113)
114 2 3 (19)
115 5 (23)
116 2 (29)
117 3 (13)
118 2 (59)
119 7 (17)
120 2 3 5
121 (11)
122 2 (61)
123 3 (41)
124 2 (31)
125 5
したがって、勝者は 105 と 120 で、それぞれ 3 つの素因数があります。ネクタイをどうするかは自分で決める必要があります。いくつかの要因が見逃されていることに注意してください。 106 の割り算、59 の割り算 118 の割り算、61 の割り算 122、そしてもちろん 101、103、107、109、113 は素数です。つまり、102、110、および 114 もリードを引き分けており、それぞれ 3 つの素因数があります。したがって、このアルゴリズムは完全ではありませんが、X と Y が 100 桁の範囲にあり、素数を 100 万または 1000 万までふるいにかけると仮定すると、答えを見逃す可能性はほとんどありません。
良い質問。私のブログですぐに探してください。