SQLで素数を抽出

　
最近SQLを勉強していますが、素数をSQLで見つけ出すテーマが面白かったのでメモしておきます。

素数という言葉を聞いたことがない人はいないと思いますが、定義は以下のとおりです。　詳細はこちらのブログを欄ください。
定義：「1より大きい整数で、1と自分自身でしか割り切れない数」

それではSQLで書いてみます。今回は素数を求めるプログラムに興味があるので、100までの素数を求めています。
具体的な処理は、２箇所に分けて行なっています。

1. 99までの連番のテーブルを作る
2. 1.のテーブルから自身より低い数字をすべて結合し、割り切れる数字が一つもない数字を選択

99までの連番テーブルの作成

CREATE TABLE Digits
 (digit INTEGER PRIMARY KEY); 

# 数字を代入
INSERT INTO Digits VALUES (0);
INSERT INTO Digits VALUES (1);
INSERT INTO Digits VALUES (2);
INSERT INTO Digits VALUES (3);
INSERT INTO Digits VALUES (4);
INSERT INTO Digits VALUES (5);
INSERT INTO Digits VALUES (6);
INSERT INTO Digits VALUES (7);
INSERT INTO Digits VALUES (8);
INSERT INTO Digits VALUES (9);

#  連番の作成
CREATE TABLE Numbers AS
SELECT D1.digit + (D2.digit * 10) AS num
FROM Digits D1 
CROSS JOIN Digits D2
WHERE D1.digit + (D2.digit * 10) BETWEEN 1 AND 100;

CROSS JOINにより自己結合で０〜９それぞれに対して０〜９を１０倍したものを足すことで、連番を作っています。

素数の抽出

SELECT
    N.num
FROM Numbers AS N
WHERE N.num > 1 
    AND 0 <> ALL
    (SELECT 
        mod(N1.num, N2.num) AS mod_num
    FROM Numbers AS N1
    CROSS JOIN Numbers AS N2 
    ON N1.num > N2.num
    WHERE N.num = N1.num AND 
                  N2.num > 1);

ALL関数に余りを入れ、WHEHRE区では、数字ごとの余りすべてが０でないという条件になっています。
「あまり全てが０ではない」　→　「割り切れるものが一つもない」

全称量化であるNOT EXISTS関数を使ったやり方は以下の書籍に書いてありました。

達人に学ぶSQL徹底指南書 第2版 初級者で終わりたくないあなたへ (CodeZine BOOKS)

SELECT num AS prime
  FROM Numbers Dividend
 WHERE num > 1
   AND NOT EXISTS
        (SELECT *
           FROM Numbers Divisor
          WHERE Divisor.num <= Dividend.num / 2
            AND Divisor.num <> 1 
            AND MOD(Dividend.num, Divisor.num) = 0)
 ORDER BY prime;