SQLで素数を抽出

スポンサーリンク

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

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

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

  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により自己結合で0〜9それぞれに対して0〜9を10倍したものを足すことで、連番を作っています。


素数の抽出


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区では、数字ごとの余りすべてが0でないという条件になっています。
「あまり全てが0ではない」 → 「割り切れるものが一つもない」

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



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;