ラッキーナンバー - これは、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…
###問題文###例 1
リーリー リーリー 説明- 最初の 3 つの価格数値の積 - リーリー 例 2
リーリー リーリー 説明- 最初の 7 つの素数の積 - リーリー 方法 1: オリジナルの方法
疑似コード
リーリー時間計算量 - O(nsqrt(n))。ここで、prime() 関数の計算量は O(sqrt(n))、nthFortunate() の for ループの計算量は O(nsqrt(n) )。
方法 2: エラトステネスのふるい
エラトステネスのふるいは、すべての素数を限界まで引き上げるために使用され、値 MAX が得られます。このメソッドでは、すべての true エントリを含むブール配列を作成し、すべての非プライム インデックスを false としてマークします。次に、配列内の最初の n 個の素数を乗算して、最初の n 個の素数の積を求めます。次に、前の方法と同様に、2 から開始し、その積に 1 を加算して、次の素数を取得します。次の素数と積の差が必要なラッキーナンバーです。
例: C 実装
空間の複雑さ - O(MAX)
###結論は###基本的な方法: 最初の n 個の素数の積を求め、その積に基づいて次の素数を計算します。素数と積の差がn番目のラッキーナンバーになります。
エラトステネスのふるい: 特定の制限に達するすべての素数を見つけて、次の素数との積を計算してラッキー ナンバーを見つけます。
以上がn番目の幸運な数字を見つけるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。