SQLで素数列挙を行う

注意: 以下のクエリはPostgresSQLで動作確認を行っています。

postgres=# select version();
                           version
-------------------------------------------------------------
 PostgreSQL 9.6.1, compiled by Visual C++ build 1800, 64-bit
(1 行)

---

いつものように仕事をさぼっていたときのこと。「さぼるにしても何かしら手を動かしておかないと周りから怪しまれるな……」なんて考えていたところ、SQLで素数列挙をしてみることを思いつきました。アリバイ工作というか偽装工作にもってこいということで、さっそく取り掛かることに。

まず自分が思いついた方法から。素数とは「1と自分以外の素数を持たない自然数」です。つまり約数の数を数えることにより素数かそうでないかを判定することができます。以下では「割る数」と「割られる数」の組み合わせを直積により求めたあと、「割る数」を約数としてその個数を数え、素数判定を行っています。

with recursive numbers (x) as (
        select 1
    union all
        select x + 1 from numbers where x < 50) -- 1..50の自然数を生成している。
select dividends.x as prime
from numbers as dividends, numbers as divisors
where divisors.x <= sqrt(dividends.x) -- 試し割り: 平方根以下まで調べれば十分
and dividends.x <> 1 -- 定義上1は素数ではない
group by dividends.x
having sum(case when mod(dividends.x, divisors.x) = 0
                then 1
                else 0 end) = 1 -- 1以外の約数を持たない
order by dividends.x;

/*
 prime
-------
     2
     3
     5
     7
    11
    13
    17
    19
    23
    29
    31
    37
    41
    43
    47
*/

さて意外にも早く書きあがってしまったため、同じことをしている人がいないかどうかを調べるべく、ネットサーフィンを始めたところ――日本でSQLを書くにあたっては避けては通れないミックさんのウェブサイトに到達。そこで示されていた解答がシンプルかつ効率もよさげだったので、自分なりに書き直してみることにしました。

with recursive numbers (x) as (
        select 2
    union all
        select x + 1 from numbers where x < 50) -- 2..50の自然数を生成している
select dividends.x as prime
from numbers as dividends
where not exists(
    select * 
    from numbers as divisors
    where divisors.x <= sqrt(dividends.x) -- 試し割り: 平方根以下まで調べれば十分
    and mod(dividends.x, divisors.x) = 0 )
order by dividends.x;

/*
 prime
-------
     2
     3
     5
     7
    11
    13
    17
    19
    23
    29
    31
    37
    41
    43
    47
*/

素数判定=約数の個数判定をnot existsを利用することにより、読みやすく、かつ効率のいいクエリになっています。まだまだSQLも奥が深いですね。もっとべんきょうせねば(´・ω・｀)