キミならどう書く 2.0 - ROUND 1 -— Lightweight Language Ringより。やっぱり俺が書くならAppleScriptだろうてことで書いてみた。基本はエラトステネスの篩なんだが、AppleScriptでリストを扱うとき、追加するのは簡単だけど取り除くのが面倒くさい上に遅くなるし、100じゃなくもっと多いときは死ぬほど遅くなる(主に最初のリストを作る時点で)ので、『素数リストと探索リスト』ではなく『素数リストと除外リスト』を作り、素数リストの最大値の二乗が探索リストの最大値を超えたら、(素数リストの一番最後の数+1)〜100から除外リストにある数字を除外して終了。なんつーか素朴だなぁw
property maxi : 100 --これを変えるとどこまで探すか変わる
on run
set nmax to maxi --nmaxには探索リストの最大値を入れておく。探索リストを作る訳じゃないけど。
set {pList, nList} to {{}, {}} --pListは素数リスト、nListは除外リスト(=非素数リスト)。
repeat with i from 2 to maxi --一応2から最大値まで回す。
log i
if i is not in nList then --iが除外リストに入っていなければ作業。
set end of pList to i --素数リストの最後にiを追加
repeat with j from 2 to nmax div i --iの倍数(i*2からi*(nmax div i))を除外リストに追加する
if (j * (item -1 of pList)) is not in nList then --除外リストに追加されるのは除外リストにない場合だけ
set end of nList to j * (item -1 of pList) ---除外リストの最後に追加
end if
end repeat
repeat while (nmax is in nList) --探索リストの最大値が除外リストに入った場合
set nmax to nmax - 1 --1ずつ減らしてみる
end repeat
end if
if ((item -1 of pList) ^ 2) > nmax then exit repeat --(素数リストの最後)^2が探索リストの最大値より大きくなったら終わり
end repeat
repeat with i from (item -1 of pList) + 1 to maxi --plistには見つかった素数が入っているが、最後(最大)のものの次から除外リストに入っていないか確認
if i is not in nList then set end of pList to i --除外リストに入っていない場合、素数リストに追加
end repeat
set CurrentDelimiter to AppleScript's text item delimiters --テキストアイテム区切りを保存
set AppleScript's text item delimiters to " " --テキストアイテム区切りをスペースに
set pList to pList as string --plistを文字列に変換
set AppleScript's text item delimiters to CurrentDelimiter --テキストアイテム区切りをもとに戻す
return pList --スペースで区切られた素数リストが出来ました
end run
探索リストを作ると遅くてかなわんのですよ。まぁ元々激しく遅い訳ですが、桁違いに遅くなる。
