シクシク素数列 Advent Calendar 2018 SQL編

この記事は、「[シクシク素数列 Advent Calendar 2018 - Qiita](https://qiita.com/advent-calendar/2018/4949prime-series)」の6日目です。
SQLでチャレンジしてみます。

## ルール
1. 数値に4か9を含む素数をシクシク素数と呼ぶ
2. 標準入力として正の整数 N を与えると N 番目までのシクシク素数を半角カンマ区切りで標準出力する
3. N は最大で 100 とする

## 解答

PostgreSQLの下記バージョンで確認しました。

```sql
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)
```

```sql: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](https://www.postgresql.jp/document/10/html/queries-with.html)を利用して2から1500までの自然数列をつくります。


```sql
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()を利用できます。

```sql
with
    t(n) as (
        select generate_series(2, 1500)
    )
select
    n
from
    t
;

  n
------
    2
    3
    4
-- 省略
 1498
 1499
 1500
(1499 rows)
```

### 自然数列から素数列をつくる

下記を参考に素数列をつくります。
[SQLで素数列挙を行う - Qiita](https://qiita.com/neko_the_shadow/items/18348d38eb3f350a9d2e)
[SQLで数学パズルを解く（数論編-解答）](http://www.geocities.jp/mickindex/database/db_puzzle_math_a.html#LocalLink-prime)

```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句に追加するだけです。

```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]'
            )
    )
select
    n
from
    prime
;

  n
------
   19
   29
   41
-- 省略
 1489
 1493
 1499
(118 rows)
```

### N番目までを取得しカンマ区切りで連結する

冒頭で示した解答です。
できるだけ標準SQLで書きたかったのですが、string_agg()は標準SQLに含まれないかもしれません、、 :disappointed_relieved:

```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を読み込み、結果を標準出力として出力するという要件を満たすかどうかは、ちょっと微妙です。

```sh
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`を書かざるを得なかったのが悔しいところです、、、 :cry: 
これは、100番目のシクシク素数列が`1319`であることをあらかじめ知っていなければわかりません。

これを避けるため、シクシク素数列を一度につくろうとして再帰CTE内に`not exists`のサブクエリを書いて試してみましたが、下記のエラーが表示されてうまくいきませんでした。
再帰CTE内ではサブクエリを利用できないようです。

なにか良いやり方はないでしょうか、、、

```sql
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
                             ^
```