素数
SQL で素数 - Life Goes On
ON句の中で色々除外してやらないと全部結びついちゃいます。
SELECT group_concat(N1.num) AS prime FROM nums N1 LEFT OUTER JOIN nums N2 ON N2.num > 1 AND N1.num / 2 >= N2.num AND N1.num % N2.num = 0 WHERE N1.num > 1 AND N2.num IS NULL;
SQLite3で動作確認
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127
4096以下の整数でかかる時間を計測すると
- 元のEXISTSを使った方法 … 0.3sec
- JOINを使った方法 … 2.0sec
やはりJOINの方はN2のN1.num/2以下の数を全部検査するので大分遅くなります。
ちなみに全約数を検査するというのも無駄なのでN1.num / 2 >= N2.numの部分を sqrt(N1.num) >= N2.numにすると両方とも大分速くなりました。(EXISTS -> 0.09, JOIN -> 0.20)