素数を求めるSQL

参考書の演習問題です。

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

演習問題

下記のテーブルから素数を求めよ

numbers

num
1
2
3
(中略)
98
99
100

テーブル作成

CREATE TABLE numbers(num INTEGER);  
INSERT INTO numbers(num) SELECT generate_series(1,100);

解答

1とその数以外で割り切れる自然数が存在しないと考えてNOT EXISTSを使います。

SELECT
  num
FROM
  numbers o 
WHERE 
  num > 1
  AND NOT EXISTS (
    SELECT
    FROM
      numbers i 
    WHERE 
      i.num < o.num
      AND i.num <> 1
      AND o.num % i.num = 0
  ) 
ORDER BY
  num
;

解答を確認したところサブクエリ内の書き方がスマートでした。

-- i.num < o.num
i.num <= o.num / 2

自分以外の約数は自分の半分以下にしか存在しない

なるほどですね。

別解

1とその数自身で割り切れるすなわち約数の個数が2個であるという発想です。

SELECT
  o.num 
FROM
  numbers o 
  INNER JOIN numbers i 
    ON o.num % i.num = 0 
GROUP BY
  o.num 
HAVING
  COUNT(o.num) = 2
ORDER BY
  o.num
;

あってるのかこれ？他にもやり方はたくさんありそう。