素数を求めるSQL
参考書の演習問題です。
演習問題
下記のテーブルから素数を求めよ
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;
あってるのかこれ?他にもやり方はたくさんありそう。