出典: Project Euler (日本語翻訳サイト)
参考: サイエンスもの置き場 プロジェクトオイラーを遊び倒すガイド(初級編)
Problem 7
素数を小さい方から6つ並べると 2, 3, 5, 7, 11, 13 であり、6番目の素数は 13 である。10001 番目の素数を求めよ。
私の解答例は以下のとおりです。
-----
def f(n): t, L = 2, [2] while len(L)<n: t += (t%2)+1 for s in L: if not t%s: break else: L.append(t) return L[-1] print f(10001)-----
素数候補を「2と、3以上の奇数」として、リストに貯めた素数で割り切れるかチェックして、全ての素数で割り切れなければ素数としてリストに追加し、n個貯まるまで続けます。
・L, t = [2], 2
初期値として、素数候補tに2、素数リストに要素2を設定します。
・while len(L)<n:
素数リストの要素数がn未満なら素数を探し続け、n個取得して終了します。
・t += (t%2)+1
素数候補tは、処理を簡単にするため「2と、3以上の奇数」とします。
演算子%は割り算の余りです。
t=2のとき、0+1累積して、次のtは3、
t=3のとき、1+1累積して、次のtは5、以降、7,9,・・・となります。
・for s in L: ~ else:
素数リストの最初から1つずつ要素を取り出して変数sにセットします。
forループを途中で抜けずに最後まで回った場合のみ、else節を行います。
・if not t%s: break
素数判定です。
素数候補を素数で割った余りがFalse(余り=0、割り切れる)の場合、for文を抜けます。このような途中抜けの場合はelse節は行いません。
全部の素数で割り切れなかった場合、else節で素数リストに素数候補を追加します。
なお、素数候補の半分の値よりも大きな数では、割り切れるわけがないので判定そのものが不要なのですが、このためにif文を1つ追加すると却って処理時間がかかったので、ここでは素数リストにある全部の素数をループで回しています。
解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
104743
(追記)
・20120716
ソースコード部分にSyntaxHighlighterを導入。
0 件のコメント:
コメントを投稿