指定された配列内のすべての要素を分割する最小の整数 > 1: C++ を使用

この記事では、整数の配列が与えられ、配列内のすべての要素を分割する 1 より大きい最小の数値を見つける必要があります。たとえば、配列 [30, 90, 15, 45, 165] の例を考えてみましょう。

リーリー

これで、配列の最大公約数 (GCD) を見つけることができます。結果が 1 の場合、つまり配列全体を 1 だけで分割できることを意味し、-1 または「不可能」を返すことができます。結果が整数の場合、この整数は配列全体を除算します。ただし、この整数は配列全体を分割する最小の整数ではない可能性があります。興味深いことに、この整数の因数も配列全体を分割しますが、これは理にかなっています。したがって、この整数の最小の因数 (GCD) を見つけることができれば、配列全体を分割する最小の整数が得られます。つまり、配列の最大公約数 (GCD) を見つける必要があり、最小の係数が答えになります。

Example

の中国語訳は次のとおりです:

Example

次の C コードは、配列内のすべての要素を分割できる 1 より大きい最小の整数を見つけます。これは、要素のリスト -

の最大公約数を見つけることで実現できます。 リーリー ＃＃＃出力＃＃＃ リーリー

Example

の中国語訳は次のとおりです:

Example

クエリが多数ある場合、数値の素因数の検索が繰り返されます。ふるい法を使用すると、数値の素因数を計算できます。

C では、1 より大きい最小の数値を見つける別の実装方法は次のとおりです。 リーリー ＃＃＃出力＃＃＃ リーリー ＃＃＃結論は＃＃＃

sqrt(n) メソッドを使用して最小係数を取得しました。これは最適化できるので、試してみてください。時間計算量は O(sqrt(n)) です。 2 番目の方法では、時間計算量は sieve 法の時間計算量、つまり O(nlog(log(n))) になります。設定した MAX グローバル変数に基づいてふるい法の上限を見つけることができることに注意してください。

以上が指定された配列内のすべての要素を分割する最小の整数 > 1: C++ を使用の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。