[AppleScript]

キミならどう書く 2.0 - ROUND 1 - 100までの整数から素数を列挙せよ@AppleScript / 2006-06-21 (水)

キミならどう書く 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

探索リストを作ると遅くてかなわんのですよ。まぁ元々激しく遅い訳ですが、桁違いに遅くなる。

[ ツッコミの受付は終了しています ]
1: midore (06-06-27 13:17)
ぐるりさん、こんにちは。
私も考えてみました。自分のとこからトラックバックうてないんでコメントしちゃってます。
2: ぐるり (06-06-27 19:44)
seedは{}でも大丈夫ですよ。
個人的にはseedがglobal変数になってるのがちょっと……ということで書き直してみた。
on run
set pList to {}
repeat with targetnum from 2 to 100
set flag to true
repeat with i in pList
if (targetnum mod i) = 0 then
set flag to false
exit repeat
end if
end repeat
if flag then set end of pList to targetnum
end repeat
return pList
end run
3: midore (06-06-27 22:32)
をー、ありがとございます。

>seedがglobal変数...
これ正直、全く意識してなかったです(;^_^ 

flagをたててるんですね。なるほどぉーです。
4: midore (06-06-27 22:46)
う?
>seedがglobal変数になってる 
とのことだったんですが、

AppleScriptではグローバル宣言しないとグローバルにならないんじゃなかったけ?
だからローカル変数ですよね?>seed
違いましたっけ?
5: ぐるり (06-06-28 03:17)
あれ、昔は暗黙のrunハンドラの中で使ってる変数はglobalになってたはず……と思ってたら微妙に違うみたい。すみませんでした。
http://homepage1.nifty.com/ton_b/tips/MISC/Inplicit.html
6: midore (06-06-28 22:31)
いぇ、今回、ぐるりさんの華麗なスクリプトをみさせてもらえてべんきょになり楽しかったです。

>http://homepage1.nifty.com/ton_b/tips/MISC/Inplicit.html
あれ、こんなすばらしいページがあったんですね。

「キミならどう書く 2.0 - ROUND 1 - 100までの整数から素数を列挙せよ@AppleScript」のリンク用URL