問題の説明
最初の素数は2、2番目の素数は3、3番目の素数は5であることがわかっています... 2020番目の素数を計算できますか？
解決
素数を見つけるというこの問題を見ると、多くの人が最初にダブルループブルートフォース検索を考えます。最初の数個のプライム番号しか見つからない場合は、このブルートフォース検索方法を使用できます。ただし、2020番目の素数と9999番目の素数を探している場合、この暴力的な方法は適用できません。
このとき、ふるい法で素数を見つけることができます。この記事では、オイラーふるい法を紹介します。原則として、素数の倍数は素数であってはなりません。したがって、素数の倍数は、素数をスクリーニングする目的を達成するために、複合数として直接マークされます。
これと同じ考え方のエゾスふるい法もありますが、エゾスふるい法には欠点があります。複合数の場合、たとえば20 = 2 * 10 = 4 * 5のように何度もふるいにかけることができます。これを改善するには、複合番号の最小のプライムファクターを使用してスクリーニングし、各複合番号が1回だけスクリーニングされるようにします。これがオイラーシーブ方式です。
ただし、各複合番号を1回だけフィルタリングする方法については、次のコードを見てみましょう。
コード：
| def ouLaShai（n）：lis = [範囲内のiに対してTrue（n + 1）]＃レコード複合番号のフィルタリングに使用lis2 = []＃範囲内のiの素数を格納（2、n + 1）：if lis [i ]：＃フィルタリングされていない場合は、Lis2に追加します。lis2のprimeのlis2.append（i）：if i * prime> n：＃n未満で、範囲を超えないことを保証しますbreak lis [i * prime] = False＃複合番号を記録しますif i％prime == 0：＃重要なステップは、各複合番号が1回だけフィルタリングされるようにすることですbreak return lis2 |
|---|
これらのコードの1つは非常に重要です。これは、各複合番号が1回だけフィルタリングされるようにするためのコードでもあります。
| if i % prime == 0: break |
|---|
i％prime == 0の場合、primeはiの素数であるため、i = x（特定の数）* primeです。次のプライム番号のいずれかがprime2をふるいにかける場合、i * prime2、i * prime2 == x * prime * prime2であるため、primeとprime2は両方ともi * prime2のプライムファクターです。ただし、prime <prime2であるため、i * prime2の最小のプライムファクターはprime2ではなくprimeです。したがって、複合番号の繰り返しのスクリーニングを回避するために、i％prime == 0の場合、直接中断します。
例：i = 2フィルター4、i = 3フィルター6および9、ただしi = 4の場合、プライムは最初に2で、8はフィルターで除外されますが、I％プライム== 0になると、直接壊れます。 、これは、prime = 3をトラバースするときに12をふるいにかけることを回避し、i = 6およびprime = 2のときに12をふるいにかけます。
**能力が強いほど、責任は大きくなります。 ****
**事実から真実を求め、厳密かつ細心の注意を払ってください。 ****
**[where2goチームが作成] **
END
インターンエディター| Wang Wenxing
責任ある編集者|喜び
Recommended Posts