素数

SQL

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)