[BigQuery]SQL로 소수 구하기

SQL 입문할 당시, 외국 사이트를 찾아다니며 스케빈저마냥 SQL 문제를 풀었는데 그 중 난이도 높았던 문제 몇 개가 생각나서 급도전해봤다.

 

 

https://www.hackerrank.com/challenges/print-prime-numbers/problem

Print Prime Numbers | HackerRank

SQL문으로 풀이하라는 문제는 링크를 찾지 못한 관계로 해커랭크 링크로 대체

 

 

WHILE 문이나 LOOP 등을 활용하는 게 일반적이지만, 프로그래밍 쪽에 더 가깝고 어차피 효율 따지는 건 이후의 문제니까 넘어가자

 

다른 레퍼런스 없이 당장 생각나는 방법으로 만드니까 아래 쿼리가 나왔다

WITH X AS (
SELECT a
FROM
	(SELECT A a, (CASE WHEN A IN (2,3) OR (A > 3 AND MOD(A,2) <> 0 AND MOD(A,3) <> 0) then 1 END) pr_yn
	FROM UNNEST(GENERATE_ARRAY(1, 1000)) A)
WHERE pr_yn = 1
)

SELECT ARRAY_TO_STRING(ARRAY_AGG(CAST(a AS STRING)), "&") prime_number
FROM
    (SELECT a, SUM(CASE WHEN mod(a, b) <> 0 THEN 0 ELSE 1 END) pr_yn
    FROM
    	(SELECT a
        FROM X)
        ,
        (SELECT a b
        FROM X)
    WHERE a >= b
    GROUP BY a
    HAVING pr_yn = 1
)

 

단락별로 살펴보면, 일단 GENERATE_ARRY() 함수로 원하는 range 만큼의 숫자를 array 형태로 생성해준 다음 UNNEST로 풀어 1000개의 자연수 행을 만들어주었다

 

동시에 소수는 2, 3이 특별한 케이스고 이후 일반적인 접근이 용이하므로 2와 3으로 분해되는 경우는 미리 WITH 절로 제거했다

 

그렇게 만들어진 임시 테이블을 서로 cross join 시켜주고 인수 분해가 2, 3 외에 다른 소수로 가능한 케이스까지 제거해주면 준비 끝

https://ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98_(%EC%88%98%EB%A1%A0)

168개 이상없이 들어있는 것 확인!

Hackerrank에서는 각 값을 하나의 값으로 합치고 구분자로 "&"를 사용하라고 했으니 마지막 변환만 해주면 완성이다

 

여러 행을 하나의 string으로 만들고 delimiter 로 "&"를 써주면 되는데, 순간 string_agg에 delimiter 옵션이 있다는 게 생각이 안나서 바보같이 array로 만들고 다시 string 변환하는 낭비를 저질렀다

STRING_AGG(CAST(a AS STRING), "&") prime_number

 

함수를 위와 같이 바꿔도 결과는 동일하다

 

 

위 방법 외에 다른 문법이나 더 쉽고 최적화된 쿼리가 생각나면 추가할 예정이다

 

P.S.

나중에 찾아보니 '에라토스테네스의 체' 라는 방법이 가장 일반적인 것으로 보였다

왜 사람들이 예전에 만든 것을 보면 부끄럽다고 하는지 알 것 같은 기분이다