SQLで素因数分解をする - Project Euler #3
PostgreSQL Advent Calendar 12/1
ついにPostgreSQL Advent Calendarが始まりました。一日目は@choplinからお届けします。
SQLはプログラミング言語である
みなさんSQLは好きですよね。
ところでSQLはRDBの操作を行うための言語だと一般的には考えられています。SQL - WikipediaによるとSQLはその為に作られた言語だそうですし、その使い方でとっても素晴らしい働きをしてくれます。
しかし、DBを用いずとも、SQL単体で様々な計算が可能だということはあまり知られていないようです。本エントリではその知られざる実力の一端をご紹介いたします。
SQLで素因数分解を行う
ご存知かとは思いますが、素因数分解とはある正の整数を素数の積の形で表すことです。
ぱっと見では中々SQLで解きにくい問題ではないでしょうか?
Project Eulerの#3が素因数分解の問題なので、実際にこれを解いてみましょう。
前準備
問題を解き始める前に、SQLでプログラミングを行う為の道具を用意しておきたいと思います。
SQLはRDBの為につくられたこともあり、関係代数をそのバックグランドとしています。集合を対象とした計算をとても素直に記述することができます。
ですが、いわゆる手続き的なロジックを記述したいこともあるでしょう。
構造化プログラミング - Wikipediaによると、構造化プログラミングでは次の3つが基本要素となります。
- 逐次
- 反復
- 分岐
これらの要素はモダンなSQLであれば満たすことが可能です。
逐次
共通表式WITH句やサブクエリで逐次的に集合を定義できます
反復
再帰SQL(WITH RECURSIVE)を使います。
再帰SQLでは前回定義した集合を基に次の集合を定義する、即ち再帰的に集合を定義することが可能です。
再帰SQLの使い方は本エントリでは詳しくは触れませんので再帰SQL — Let's Postgresなどを参照して下さい。
分岐
CASE式を用いると、任意の条件に応じて集合を定義することができます。
道具は揃った
以上の3要素を組み合わせることで、SQLでも手続き的な記述を行うことが可能です。
これらを利用して素因数分解を行いましょう。
※3要素の内容については個人的に思いついたものを挙げてみました。他にもっといいやり方があれば教えて下さい。
戦略
素因数分解を行うアルゴリズムはいくつか知られているようですが、今回は最も単純な
"小さい素数から順に因数かどうか判定していく"
という方法を採用します。
この方向で素因数分解を行うために、次の2つの問題に分割します。
1.は自明かと思います。素因数分解の為には高々二乗根までの素数があれば十分です。
2.についてですが、単純に素数集合から割り切れるものを取り出すだけでは不十分です。複数回割り切れる素数が存在することがある為です。それぞれの素数が対象の数を何回割り切るかを判定する必要があります。
これらの二つの問題をSQL関数として実装しました。
PostgeSQLとの関係は?
PostgreSQLはRDBの中でもSQL標準で定められた構文を比較的多く実装しています。その為、SQLのみで逐次、反復、分岐の三要素を満たすことができます。(再帰SQLなどは実装されていないRDBもあります)
また、
- 配列を扱える
- generate_seriesが強力
- SQLで関数を組める
なども等もSQLでプログラミングを行う上で大きな力となります。
つまり、PostgreSQLはSQLの処理系として優れた実力を持っている、ということです