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から始まる自然数列をつくる

再帰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に含まれないかもしれません、、 :disappointed_relieved:

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を書かざるを得なかったのが悔しいところです、、、 :cry:
これは、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
                             ^
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