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