SQLで素因数分解をする - Project Euler #3

PostgreSQL Advent Calendar 12/1

ついにPostgreSQL Advent Calendarが始まりました。一日目は@choplinからお届けします。

SQLプログラミング言語である

みなさんSQLは好きですよね。

ところでSQLRDBの操作を行うための言語だと一般的には考えられています。SQL - WikipediaによるとSQLはその為に作られた言語だそうですし、その使い方でとっても素晴らしい働きをしてくれます。

しかし、DBを用いずとも、SQL単体で様々な計算が可能だということはあまり知られていないようです。本エントリではその知られざる実力の一端をご紹介いたします。

SQL素因数分解を行う

ご存知かとは思いますが、素因数分解とはある正の整数を素数の積の形で表すことです。

ぱっと見では中々SQLで解きにくい問題ではないでしょうか?

Project Eulerの#3が素因数分解の問題なので、実際にこれを解いてみましょう。

前準備

問題を解き始める前に、SQLでプログラミングを行う為の道具を用意しておきたいと思います。

SQLRDBの為につくられたこともあり、関係代数をそのバックグランドとしています。集合を対象とした計算をとても素直に記述することができます。

ですが、いわゆる手続き的なロジックを記述したいこともあるでしょう。

構造化プログラミング - Wikipediaによると、構造化プログラミングでは次の3つが基本要素となります。

  • 逐次
  • 反復
  • 分岐

これらの要素はモダンなSQLであれば満たすことが可能です。

逐次

共通表式WITH句やサブクエリで逐次的に集合を定義できます

反復

再帰SQL(WITH RECURSIVE)を使います。

再帰SQLでは前回定義した集合を基に次の集合を定義する、即ち再帰的に集合を定義することが可能です。

再帰SQLの使い方は本エントリでは詳しくは触れませんので再帰SQL — Let's Postgresなどを参照して下さい。

分岐

CASE式を用いると、任意の条件に応じて集合を定義することができます。

道具は揃った

以上の3要素を組み合わせることで、SQLでも手続き的な記述を行うことが可能です。
これらを利用して素因数分解を行いましょう。

※3要素の内容については個人的に思いついたものを挙げてみました。他にもっといいやり方があれば教えて下さい。

戦略

素因数分解を行うアルゴリズムはいくつか知られているようですが、今回は最も単純な

"小さい素数から順に因数かどうか判定していく"

という方法を採用します。

この方向で素因数分解を行うために、次の2つの問題に分割します。

  1. 与えられた整数の二乗根を上限とする素数集合を求める
  2. 素数集合に対し順に因数かどうかの判定を行う

1.は自明かと思います。素因数分解の為には高々二乗根までの素数があれば十分です。

2.についてですが、単純に素数集合から割り切れるものを取り出すだけでは不十分です。複数回割り切れる素数が存在することがある為です。それぞれの素数が対象の数を何回割り切るかを判定する必要があります。

これらの二つの問題をSQL関数として実装しました。

1.素数集合を求める

素数を求める為のアルゴリズムは多くのものが知られています。

今回は単純なエラトステネスのふるいを採用しています。

2.素数集合に対し、順に因数かどうかの判定を行う

再帰SQLを用いて、素数集合の要素に対し順番にわり切れるかどうかの判定しています。上で述べたように、一度割り切れた素数はもう一度判定を行なっています。

実行!

2.で素因数の集合を返す関数にしているので、関数を実行するだけです。

これで無事SQL素因数分解を行うことができました。

PostgeSQLとの関係は?

PostgreSQLRDBの中でもSQL標準で定められた構文を比較的多く実装しています。その為、SQLのみで逐次、反復、分岐の三要素を満たすことができます。(再帰SQLなどは実装されていないRDBもあります)

また、

  • 配列を扱える
  • generate_seriesが強力
  • SQLで関数を組める

なども等もSQLでプログラミングを行う上で大きな力となります。

つまり、PostgreSQLSQLの処理系として優れた実力を持っている、ということです

結論

SQL! SQL!

明日は

PostgreSQL Advent Calendar 明日の担当はumitanukiさんです。よろしくお願いします!