シクシク素数アドベントカレンダー sed 編

はじめに

同日公開の合成数列の和アドベントカレンダー sed 編から色々流用して組みましたので、詳しくはそちらもご覧ください。
なお、こっちにはポエムはありません。

ルール

• 数値に4か9を含む素数をシクシク素数と呼ぶことにします
  • 19とか41とか149とか。
• 標準入力として正の整数 N を与えたら N 番目までのシクシク素数を半角カンマ区切りで標準出力してください
  • 例 N = 9 の場合、19,29,41,43,47,59,79,89,97
• N は最大で 100 とします

ソース

prime49.sed

# 数値を同じ文字数のXに変える
:Ln2x
 s/$/  9z8z7z6z5z4z3z2z1z0/
 s/^(.)(.* .*) [^ ]*\1([^ ]*)$/\2\3/
 s/X/XXXXXXXXXX/g
 y/z/X/
 /^ /!b Ln2x
s/[^X]//g
# 素数判定用の Y の塊と、数値の0～9をa～jに変換した文字列を用意
s/.*/Y & b/
:Lmain
 # 2加算処理
 s/^/YY/; T
 s/ (j*)j$/ b\U\1\Lb/; t Lup
 s/([^ j])(j*)j$/\U\1\2\Lb/; T Lnoup
 # 繰り上がり有り
 :Lup
 y/ABCDEFGHIJ/bcdefghija/
 b Lpost
 # 繰り上がり無し
 :Lnoup
 s/.$/\U&/; T
 y/BDFH/dfhj/
 :Lpost
 # 4,9 ( 対応する e,j ) の有無をチェック
 /[ej]/! b Lmain
 # 3以上の奇数で試し割りして素数判定
 s/YYY/YYY /
 :Ltry
  T; s/^(Y+) (\1+ )/\1\2/; t Lmain
  s/ YY/YY /
  /^(Y+) \1{4}/b Ltry
 s/ //
 # ホールドスペースに行毎追加
 H
 # 指定の個数たまるまでループ
 T; s/XX/X/; t Lmain
x
s/[XY ]//g
s/\n//
# 最後に数字に戻す
y/abcdefghij\n/0123456789,/
# ここで出力

出力例

$ sed -rf prime49.sed <<< 2
19,29
$ sed -rf prime49.sed <<< 10
19,29,41,43,47,59,79,89,97,109
$ sed -rf prime49.sed <<< 100
19,29,41,43,47,59,79,89,97,109,139,149,179,191,193,197,199,229,239,241,269,293,347,349,359,379,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,509,541,547,569,593,599,619,641,643,647,659,691,709,719,739,743,769,797,809,829,839,859,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1019,1039,1049,1069,1091,1093,1097,1109,1129,1193,1229,1249,1259,1279,1289,1291,1297,1319

解説

大体合成数列の和アドベントカレンダー sed 編と似たようなことをやっています。

ただし、こちらは和ではなく抽出が主目的です。
そこで、YYYYY→5のような、文字列の長さ→数字の変換を毎回行うのではなく、別途数字のカウントアップを実装することにしました。それにより4,9が含まれているかどうかの判断を先に行います。

基本的なアイデアはこうです。

• 0～9の代わりにa～jの文字を使う
• カウントアップに伴い影響を受ける桁を大文字化し、後の変換対象を識別する
  • 繰り上がりがある場合、例えば12999→13001ではbcjjj→bdaabになりますが、このように変換を行います
    • bcjjj
    • →bCJJb(最下位の変換+影響範囲の大文字化)
    • →bdaab(yコマンドによるA～I,J→b～j,aのスライド)
  • 繰り上がりがない場合、末尾のみを大文字化し、そののち+2相当の変換を行う ( yコマンドによるB,D,F,H→d,f,h,jのスライド )
• 繰り上がりにより桁数が増える場合、先頭に 0 に相当する a を予め追加しておく

なお、a～j の表現そのままホールドスペースに追加していきますので、最後に数字に戻してから出力します。

性能問題

ところで、sed の用いるExtended-REのエンジンがそれほど速くない上に、この問題では最大1319の素数判定を行うため、素数判定のループ回数が結構嵩みます。
…ということで、今回の実装では、入力100の時手元のPCで25秒、ideone.com でも9秒近くの時間を要しました。

まあ、高速化するだけなら、( 最大の素数が1319と分かってることもあり ) 色々手はあるのですが、実装の分かり易さを取り、今回は見送りました。

興味のある人は、色々と試してみても面白いかもしれませんね。