PE #005, #003, #007 in J
昨日 (id:flappphys:20080324#p2) の続きで，「20以下の自然数全てで割り切れる最小の自然数」．
せっかく再帰を覚えたのに，Jは末尾再帰をループに変換しないらしく，3000段くらいでstack errorになる．例えば1から順に数え上げるループで，第 i 番目の数の20以下の全ての自然数による剰余を求めて，そのorを取ればいずれは発見できる... というプログラム：
]`($:@>:) @. (+./@(*@((1+i.10)&|))) 1 2520 ]`($:@>:) @. (+./@(*@((1+i.11)&|))) 1 |stack error | ]`($:@>:)@.(+./@(*@((1+i.11)&|)))1
そこでdo-whileループ相当のイディオムを覚えた：
(>: ^: (+./@(*@((1+i.10)&|))) ^: _) 1 2520 (>: ^: (+./@(*@((1+i.11)&|))) ^: _) 1 27720 (>: ^: (+./@(*@((1+i.12)&|))) ^: _) 1 27720 (>: ^: (+./@(*@((1+i.13)&|))) ^: _) 1 360360
これは「13以下の自然数全てで...」くらいの問題サイズで明らかに実行時間が辛くなってくる．仕方ないので除数を素因数分解して必要な因数を調べ，それらを掛け合わせる．Jには素数関連のルーチンが組み込まれているので楽勝：
*/@(p:@i. ^ >./@(q: >:@i.)) 20x 232792560
p: i は第 i 番目の素数を返し，m q: n は最初の m 個の素数を使って n を素因数分解した結果の指数の配列を返す．20x は多倍長整数リテラル．
#003と#007は上記のverbを使って瞬殺．素数関連には色々アルゴリズムがあるようで興味を惹かれるが，似たようなことは以前にも度々やってるし，見つけた素数の表の管理とかがうざいので無視．
