BigQueryのSQLã§ãªã‚“ã¨ãªãç´ æ•°åˆ—æŒ™ã‚’è©¦ã—ãŸ(実用性皆無)

GENERATE_ARRAY()関数を使うと等差数列が作れるので後はJOINしてがんばるだけ

前に以下の記事でエラトステネスのふるいなどを調べたが、SQLでは試し割りによる方法ぐらいしか書けそうになかった
sucrose.hatenablog.com

試し割り

ある数をその数よりも小さな1以外の数で実際割ってみて、割り切れなければ素数。
これをすべての数について確かめる
以下のクエリを動かしてみたら、判定したい最大の数を\(N\)とした時\(N\)を倍にしたら実行時間は4倍ぐらい増えていた(\(O(N^2)\)っぽい雰囲気)
なので最大でも数万ぐらいまでしか計算できなかった

#standardSQL

#数列を作る
WITH numbers AS (
  SELECT
    i
  FROM UNNEST(GENERATE_ARRAY(3, 20000, 2)) AS i
)
#割り切れるか試す
, divisible AS (
  SELECT
    a.i
    , MOD(a.i, b.i) = 0 AS is_divisible
  FROM numbers AS a
  JOIN numbers AS b
  ON SQRT(a.i) + 1 > b.i
)

#1回も割り切れていないものが素数
SELECT * FROM UNNEST([2, 3]) AS i
UNION ALL
SELECT
  i
FROM divisible
GROUP BY i
HAVING NOT LOGICAL_OR(is_divisible)
ORDER BY i