\(\mathrm\TeX\)配列を使って素数リストをひたすら生成

前回配列が扱えるようになったので満を持して素数探索プログラムを書こう。これならただ計算してるだけよりわざわざ\(\mathrm\TeX\)で書く意義がありそうな気がするよ！素数リスト使って問題作るとか！

とりあえず高速化とかほとんど考えないでnまでの素数を列挙するマクロを作ってみる

1. \def\PrimeCount#1{%
2.         \NewArray{primes} \PushArray{primes}{2}% 配列primes生成、2をpush(=要素として加える)
3.         \newcount\@judnum \@judnum=3\relax% カウンタ\@judnumを生成、3を代入
4.         \newcount\@aryind% カウンタ\@aryindを生成　※余計にカウンタを生成し過ぎないようループの前で生成する
5.         \@whilenum\@judnum<#1\relax \do{% \@judnumが引数nを超えないときループ
6.                 \@aryind=0\relax%
7.                 \LengthofArray[\arylen]{primes}% primesの長さ を\arylenに格納　※\arylenはカウンタではなく制御綴。
8.                 \@tempcntb=0\relax% \@tempcntbを、\@judnumが素数か判別するboolean変数として使用　
9.                 \@whilenum\@aryind<\arylen\relax \do{% \@judnumが素数かどうか判別するループ
10.                         \GetArray[\ttt]{primes}{\the\@aryind}% 素数リストを順に調べていく　\tttにprimesを格納
11.                         \@tempcnta=\@judnum% 計算のため\@tempcntaに値をコピー
12.                         \surplus\@tempcnta\ttt\relax% 以前作った\surplusで\@tempcnta % \tttを計算
13.                         \ifnum\@tempcnta=\z@% 割り切れたなら\@tempcndb=1にする&　\@aryindを増やしてloopを終わらせる
14.                                 \@tempcntb1\relax%
15.                                 \advance\@aryind\arylen%
16.                         \fi%
17.                         \increment\@aryind%
18.                 }%
19.                 \ifnum\@tempcntb=\z@ \PushArray*{primes}{\the\@judnum} \fi% ↑で\@tempcndb=1になっていなければ素数
20.                 \advance\@judnum2% 偶数は飛ばす
21.         }%
22.         [\ShowArray{primes}]%
23. }%

配列TLArrayパッケージの仕様は作者のブログで確認してもらうとして、カウンタの宣言がループの外になっているのは、ループの中でカウンタを作るとループを繰り返す毎にカウンタを使用してしまうからである。\(\mathrm\TeX\)のカウンタは最大256個、\(\mathrm\LaTeX\)のオプションを使っても数万個しか使えない。もともとペーシ数とか数えるのに使う機能だしシカタナイネ
　ここで問題になるのは以前作った\surplusがカウンタを3つも使っている上に一番激しいループの中にいることだ。
　ひとまず引数をわざわざ新しいカウンタで受けている部分は激しくもったいないので引数を直接使うとして、それでも一つはカウンタが必要にになる。

1. \def\surplus#1#2{%
2.         \newcount\t \t=#1\relax%
3.         \divide#1#2 \multiply#1#2 \advance\t-#1%
4.         #1=\t\relax%
5. }

これを使うとn=800くらいが限界になる。

(No room for a new \count はカウンタがもう作れないというエラー)

4桁も無い素数リストなどショボいにも程が有るのでもう少し改善を試みる。

　本体の\PrimeCountと同様カウンタを"外で"作ってしまえばいい、つまりJavaでいうクラス変数みたいな感じにすればよろしい。Javaでもストリームリーダーとかを作りすぎてメモリを浪費しないようにクラスで宣言することがある。
　流石に \t とかいう適当な名前だとスコープが広がってどっかで名前が被りそうな気がするので名前を複雑にして

1. \newcount\suptmp
2. \def\surplus#1#2{%
3.         \suptmp=#1\relax%
4.         \divide#1#2 \multiply#1#2 \advance\suptmp-#1%
5.         #1=\suptmp\relax%
6. }

こうすればn=1000でも10000でも動くようになる。




　さて、ここからは高速化を図る。素数以外の数では割っていないのでこれでもかなり速めだが、
nの約数pは\(\sqrt n\) までに現れなければそれと対になる\(\frac{n}{p}\)も無いからそれより先を計算しても割り切れることはないはずである。
というわけで\(\sqrt n\)までで計算を止めたいが剰余すらなかった\(\mathrm\TeX\)に平方根計算などど言う高級なものがあるわけもなく、ニュートン法やら二分探索やらを使ったらできるんだろうが今回は\(p^2\)がnを超えないという条件を使う。(またpのためにカウンタを用意しなければいけないが)

\newcount\@tespow

を4行目の後、

\@tespow=\ttt \multiply\@tespow\ttt\relax
\ifnum\@tespow>\@judnum \advance\@aryind\arylen\relax \fi

を11行目の後におけばループはpが\(\sqrt n\)を超えたところでbreakされる。

結果はn=10000の時
元の関数が11秒
改良した物が1.7秒
だった(\(\mathrm\TeX\)では計時機能が分単位なのでストップウォッチで計ることになったが)
めっちゃ速くなったなびっくり

おかげでn=100000でも数十秒でできた。
24ページに渡る素数リストもできたし時間をかければいくらでも増やせそうなので今回は満足。

-2019-03-12: \(\TeX\)を\(\mathrm\TeX\)に変更