SQLで数字パズルをする #PostgreSQL

環境: postgresql 9.6

以下のサイトでSQLで解くパズルがいくつか紹介されていたので、簡単なものを挑戦してみます
https://oraclesqlpuzzle.ninja-web.net/index.html

1. 素数を求めるには?

プログラミングの入門でよくありそうな問題。
numberテーブルに連続した自然数(1~1000)がnumカラムに入っている。その中から素数だけを取り出す。

前準備

テーブルを作成して連続した自然数を1000個入れる

create table number (num INTEGER);
insert into number(num) values (select generate_series(1,1000));

解き方

素数は

1以外の自然数で割り切れない自然数N

なので

自然数N に対して 2->(N-1)までの自然数で割り算をして、その時の剰余が全て0にならないこと

を確認すればOKです。

このままでもOKですが計算量を減らすために割る時の自然数の2乗が自然数Nを超過しないことも条件に入れます

自然数N に対して 2->(N-1)までの自然数で割り算をして、その時の剰余が全て0にならないことこのループを伴う処理はnot existsを使いましょう。

解答

not existsを使ってループ処理をするのがポイントです。

select 
  s1.num 
from 
  number as s1 
where 
  s1.num > 1
and not exists(
    select s2.num from number as s2
    where 
      s1.num >= s2.num * s2.num 
    and 
      s2.num > 1 
    and 
      s1.num % s2.num = 0 
    limit 1
  )
;

2. 組み合わせの問題①

数字 8,7,4,2,1,0 のうち
3つを足して10になる組み合わせをすべて求める。

前準備

テーブルを作成して必要な自然数を入れる

create table number (num INTEGER);
insert into number (num) values(1),(2),(0),(4),(7),(8);

解き方

３つの組み合わせを同じtableをinner joinする(順列じゃないのでt1.num < t2.numで除外処理を入れる)
組み合わせが完了してからwhere句で合計値が10になるものを取り出す

解答

先にinner joinで組み合わせのtableを作成するのがポイントです。

select 
  t1.num, t2.num, t3.num, t1.num+t2.num+t3.num as sum  
from 
  number as t1
inner join  
  number as t2
on 
  t1.num < t2.num 
inner join 
  number as t3 
on 
  t2.num < t3.num 
where 
  t1.num + t2.num + t3.num = 10;

結果

num	num	num	sum
1	2	7	10
0	2	8	10

(2 rows)

3. 組み合わせ問題②

数字 21,12,17,11,25,10,3,7,15 のうち
2つの数字を足して、
2,3,5,7,11で割り切れない数になる組み合わせをすべて求める。

前準備

テーブルを作成して必要な自然数を入れる


create table number (num INTEGER);
insert into number (num) values(21),(12),(17),(11),(25),(10),(3),(7),(15);

解き方

①ができればほとんど同じですね。

2つの組み合わせを同じtableをinner joinする(順列じゃないのでt1.num < t2.numで除外処理を入れる)
組み合わせが完了してからwhere句で合計値がそれぞれ割り算する

解答

select 
  t1.num, t2.num, t1.num+t2.num as sum 
from 
  number as t1
inner join 
  number as t2
on 
  t1.num < t2.num 
where 
  (t1.num+t2.num) % 2 != 0 
and 
  (t1.num+t2.num) % 3 != 0 
and 
  (t1.num+t2.num) % 5 != 0 
and 
  (t1.num+t2.num) % 7 != 0 
and 
  (t1.num+t2.num) % 11 != 0 
;

結果

num	num	sum
12	17	29
12	25	37
11	12	23
10	21	31
3	10	13
7	12	19
7	10	17

(7 rows)

感想

inner joinで同じテーブル繋げられるの初めて知りました。数独もsqlで解けるらしいので、今度チャレンジしてみようと思います。