Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.

この記事は、「シクシク素数列 Advent Calendar 2018 - Qiita」の6日目です。
SQLでチャレンジしてみます。

## ルール

1. 数値に4か9を含む素数をシクシク素数と呼ぶ
2. 標準入力として正の整数 N を与えると N 番目までのシクシク素数を半角カンマ区切りで標準出力する
3. 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から始まる自然数列をつくる

```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を含む素数を取得する

```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"
```

### 入出力

```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`のサブクエリを書いて試してみましたが、下記のエラーが表示されてうまくいきませんでした。

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

```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
^
```
Why not register and get more from Qiita?
1. We will deliver articles that match you
By following users and tags, you can catch up information on technical fields that you are interested in as a whole
2. you can read useful information later efficiently
By "stocking" the articles you like, you can search right away