APL/J言語での素数


数日前にJ言語では素因数分解がすごくカンタンという話を書きました。

   q:978187098701
5573 175522537
   q:123456789
3 3 3607 3803

つまりq:(キューコロン)という単項動詞を使います。
ところで、素数を発生させる動詞もあるだろうと探したらp:(ピーコロン)というのがありました。これが不思議で素数に連番が振ってあるらしく、数字を与えるとその番号の素数を返します。

   p:0
2
   p:10
31
   p:907987
13965059
   p:!10
61194733
   p:i.10
2 3 5 7 11 13 17 19 23 29
   p:0 1 2 3 4 5 6 7 8 9 10
2 3 5 7 11 13 17 19 23 29 31

という中でたとえば、1000以上9999の素数を調べたいときにはどうしたらいいのだろうか。これでは範囲が大きすぎるので1000以上1010以下にしよう。

   p:100
547
   p:1000
7927
   p:500
3581
   p:250
1597
   p:200
1229
   p:150
877
   p:175
1049
   p:160
947
   p:(165+i.10)
983 991 997 1009 1013 1019 1021 1031 1033 1039

というわけで1009だけでした。

以上

追記:20090302
素数は無限にあるらしいですが、だんだんその間隔は開いていくのですよね? えっと、言いたいのは最初の1から1000までにある素数の数と、たとえば1万から1万1千までの間にある素数の数は後者の方が圧倒的に少ないはず。さて、10万から10万1千までの素数の数はもうちょっとしかのこtっていないかもしれない。こんな疑問を解いてみよう!
とりあえず、10000番目の素数はいくつか調べたい。p:10000ですが、いったん配列に入れて、最後の要素を調べたい。配列の要素を見るのは{(波カッコ、ブレイス)ですが、これにドット(ピリオド)やコロンをつけるといろいろできます。{:(波カッココロン)が目的の最後の要素を返す動詞でした。

   p:10000
104743
   {:p:i.10000
104729
   p:9999
104729
   +array=.p:i.10000
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79

解説:i.nは0からn-1までの整数の配列。この場合は0 1 ... 9999だったのですね。とりあえずこの結果を配列に入れます。
次に、大なり小なりでフラグをたてれば0と1の配列になるので、ある数以上、ある数以下の素数の数がわかります。0から1000までと、1000から2000まで、とかいろいろやってみる。ANDは*.(アスタリスクドットです)

168
   +/(array > 1000)*(array < 2000)
135
   +/(array > 9000)*(array < 10000)
112
   +/(array > 100000)*(array < 101000)
81

うむ。数を大きくしてもあまり分布が減りませんね。また考えよう。
以上