この記事は、「シクシク素数列 Advent Calendar 2018 - Qiita」の6日目です。
SQLでチャレンジしてみます。
ルール
- 数値に4か9を含む素数をシクシク素数と呼ぶ
- 標準入力として正の整数 N を与えると N 番目までのシクシク素数を半角カンマ区切りで標準出力する
- N は最大で 100 とする
解答
PostgreSQLの下記バージョンで確認しました。
postgres=# select version();
version
----------------------------------------------------------------------------------------------------------------------------------
PostgreSQL 11.1 (Debian 11.1-1.pgdg90+1) on x86_64-pc-linux-gnu, compiled by gcc (Debian 6.3.0-18+deb9u1) 6.3.0 20170516, 64-bit
(1 row)
4949primeseq.sql
with recursive
t(n) as (
values(2)
union all
select
t.n + 1
from
t
where
t.n + 1 <= 1500
),
prime(n) as (
select
t1.n
from
t t1
where
not exists (
select 1
from
t t2
where
t2.n <= sqrt(t1.n) and
mod(t1.n, t2.n) = 0
) and
(
cast(t1.n as varchar) ~ '[49]'
)
),
"4949prime" as (
select
n
from
prime
order by
n
limit
:count
)
select
string_agg(cast(n as varchar), ',' order by n) as "4949seq"
from
"4949prime"
解説
2から始まる自然数列をつくる
再帰CTEを利用して2から1500までの自然数列をつくります。
with recursive
t(n) as (
values(2)
union all
select
t.n + 1
from
t
where
t.n + 1 <= 1500
)
select
n
from
t
;
n
------
2
3
4
-- 省略
1498
1499
1500
(1499 rows)
PostgreSQLならば、generate_series()を利用できます。
with
t(n) as (
select generate_series(2, 1500)
)
select
n
from
t
;
n
------
2
3
4
-- 省略
1498
1499
1500
(1499 rows)
自然数列から素数列をつくる
下記を参考に素数列をつくります。
SQLで素数列挙を行う - Qiita
SQLで数学パズルを解く（数論編-解答）
with recursive
t(n) as (
values(2)
union all
select
t.n + 1
from
t
where
t.n + 1 <= 1500
),
prime(n) as (
select
t1.n
from
t t1
where
not exists (
select *
from
t t2
where
t2.n <= sqrt(t1.n) and
mod(t1.n, t2.n) = 0
)
)
select
n
from
prime
;
n
------
2
3
5
7
-- 省略
1489
1493
1499
(239 rows)
4または9を含む素数を取得する
正規表現で4または9を含むものを条件としてwhere句に追加するだけです。
with recursive
t(n) as (
values(2)
union all
select
t.n + 1
from
t
where
t.n + 1 <= 1500
),
prime(n) as (
select
t1.n
from
t t1
where
not exists (
select *
from
t t2
where
t2.n <= sqrt(t1.n) and
mod(t1.n, t2.n) = 0
) and
(
cast(t1.n as varchar) ~ '[49]'
)
)
select
n
from
prime
;
n
------
19
29
41
-- 省略
1489
1493
1499
(118 rows)
N番目までを取得しカンマ区切りで連結する
冒頭で示した解答です。
できるだけ標準SQLで書きたかったのですが、string_agg()は標準SQLに含まれないかもしれません、、 
with recursive
t(n) as (
values(2)
union all
select
t.n + 1
from
t
where
t.n + 1 <= 1500
),
prime(n) as (
select
t1.n
from
t t1
where
not exists (
select *
from
t t2
where
t2.n <= sqrt(t1.n) and
mod(t1.n, t2.n) = 0
) and
(
cast(t1.n as varchar) ~ '[49]'
)
),
"4949prime" as (
select
n
from
prime
order by
n
limit
:count
)
select
string_agg(cast(n as varchar), ',' order by n) as "4949seq"
from
"4949prime"
入出力
上記SQLを4949primeseq.sqlというファイルに保存し、psqlコマンドでバインド引数（count）を渡してファイルを実行します。
標準入力からNを読み込み、結果を標準出力として出力するという要件を満たすかどうかは、ちょっと微妙です。
psql -U postgres -f 4949primeseq.sql -v count=10
4949seq
--------------------------------
19,29,41,43,47,59,79,89,97,109
(1 row)
psql -U postgres -f 4949primeseq.sql -v count=100
4949seq
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
-------------------------------------------------
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,5
47,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,1
129,1193,1229,1249,1259,1279,1289,1291,1297,1319
(1 row)
まとめ
SQLでも素数列を得ることができました。
ただ、最初に自然数列をつくるにあたって、再帰CTEを終了させるためにt.n + 1 <= 1500を条件としており、マジックナンバー1500を書かざるを得なかったのが悔しいところです、、、 
これは、100番目のシクシク素数列が1319であることをあらかじめ知っていなければわかりません。
これを避けるため、シクシク素数列を一度につくろうとして再帰CTE内にnot existsのサブクエリを書いて試してみましたが、下記のエラーが表示されてうまくいきませんでした。
再帰CTE内ではサブクエリを利用できないようです。
なにか良いやり方はないでしょうか、、、
with recursive
t(n) as (
values(2)
union all
select
t1.n
from
t t1
where
not exists (
select *
from
t t2
where
t2.n <= sqrt(t1.n) and
mod(t1.n, t2.n) = 0
)
limit
100
)
select
n
from
t
;
ERROR: recursive reference to query "t" must not appear within a subquery
LINE 13: t t2
^