SQLで素数列挙

SQLで素数を列挙する

SQLパズルです。素数を列挙します。
1から適当な数字まで並んだ数列を含むテーブルSEQがあります。

SELECT * FROM SEQ;

1から100までを用意しました。

num
1
2
3
4
5
6
7
(中略)
.
.
.
100

この1から100の数列から、素数を列挙するクエリを書いてみましょう。

素数列挙　戦略

素数になる条件を書き出して、否定してNOT EXISTS, という戦法でいきます。

自然数$N$が素数になる条件は、「1と$N$の2つでしか割り切れない」です。

否定してみると、「$1 \lt M \leq \sqrt{N}$なる整数$M$で、$N$を割り切るものがある」ですかね。

なので、このような$M$が存在しない、というクエリを書けばよさそうです。

素数列挙　クエリ

NOT EXISTSを使って、こんな感じです。

SELECT 
  s1.num
FROM 
  SEQ s1
WHERE
  s1.num > 1
AND
  NOT EXISTS(
    SELECT 
      *
    FROM 
      SEQ s2
    WHERE 
      s1.num >= s2.num * s2.num
    and 
      s2.num > 1
    and 
      s1.num % s2.num = 0
  );

結果です。ちゃんと素数ができています！

num
2
3
4
5
7
11
13
17
19
23
(中略)
.
.
.
97

感想

素数になる条件を考えて、否定してNOT EXISTS、という流れで考えると上手くいきました。

結合しないのに複数のテーブルを持ちだすクエリの作成は、頭を使いますね...

いいパズルでした。

参考文献

達人に学ぶSQL徹底指南書
http://www.amazon.co.jp/達人に学ぶ-SQL徹底指南書-ミック-ebook/dp/B00DIM6330