n番目の幸運な数字を見つける

ラッキーナンバー - これは、m > 1 である最小の整数です。与えられた正の整数 n の場合、pn# m は素数です。ここで、pn#最初の n 個の積素数です。

たとえば、3 番目の幸運な数字を計算するには、最初に最初の 3 つの素数 (2、3、5) の積である 30 を計算します。 2 を加算すると 32 となり、偶数になります。3 を加算すると、33 となり、3 の倍数になります。 6 までの整数も除外できます。 7 を加えると 37 が得られ、これは素数です。したがって、7は3番目の幸運な数字です。

最初の元の数字のラッキーナンバーは -

です

3、5、7、13、23、17、19、23、37、61、67、61、71、47、107、59、61、109…

＃＃＃問題文＃＃＃

数値 n を与えます。 n 番目の幸運な数字を見つけます。

例 1

リーリー リーリー

説明

- 最初の 3 つの価格数値の積 - リーリー 例 2

リーリー リーリー

説明

- 最初の 7 つの素数の積 - リーリー 方法 1: オリジナルの方法

この問題を解決する簡単な方法は、最初に最初の n 個の素数の積である pn# を計算し、次に pn# と次の素数の差を求めることです。得られた差額がラッキーナンバーとなります。

疑似コード

リーリー

例: C 実装

次のプログラムでは、最初の n 個の素数のプリミティブを計算し、そのプリミティブの後の次の素数を見つけることによって、ラッキー ナンバーが計算されます。ラッキーナンバーは、次の素数と原始数の差です。

リーリー ＃＃＃出力＃＃＃ リーリー

時間計算量 - O(nsqrt(n))。ここで、prime() 関数の計算量は O(sqrt(n))、nthFortunate() の for ループの計算量は O(nsqrt(n) ）。

空間の複雑さ - O(1)

方法 2: エラトステネスのふるい

エラトステネスのふるいは、すべての素数を限界まで引き上げるために使用され、値 MAX が得られます。このメソッドでは、すべての true エントリを含むブール配列を作成し、すべての非プライム インデックスを false としてマークします。次に、配列内の最初の n 個の素数を乗算して、最初の n 個の素数の積を求めます。次に、前の方法と同様に、2 から開始し、その積に 1 を加算して、次の素数を取得します。次の素数と積の差が必要なラッキーナンバーです。

疑似コード

リーリー

例: C 実装

次のプログラムでは、サイズ MAX のブール素数配列に MAX より前のすべての素数が記録されます。次に、最初の n 個の素数を乗算することで元の値が求められます。次に、前の方法と同様に、nextPrime を見つけます。 nextPrime と Product の違いはラッキーナンバーです。

リーリー ＃＃＃出力＃＃＃ リーリー

時間計算量 - O(n log(log(n)))

空間の複雑さ - O(MAX)

＃＃＃結論は＃＃＃

まとめると、n 番目のラッキーナンバーは次の 2 つの方法で見つけることができます。

基本的な方法: 最初の n 個の素数の積を求め、その積に基づいて次の素数を計算します。素数と積の差がn番目のラッキーナンバーになります。

エラトステネスのふるい: 特定の制限に達するすべての素数を見つけて、次の素数との積を計算してラッキー ナンバーを見つけます。

両方の方法は、単純に変数サイズの制限により、n の値が小さい場合に有効です。値が大きい場合は、より効率的で最適化されたソリューションが必要になります。

以上がn番目の幸運な数字を見つけるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。