[HackerRank] Print Prime Number 풀이 (Oracle)

문제

Print Prime Numbers | HackerRank

Print Prime Numbers | HackerRank

1000 보다 작거나 같은 소수를 출력하는 쿼리를 작성합니다.

결과를 한 줄로 인쇄하고 '&' 문자를 구분 기호로 사용합니다.

예시) 10보다 작거나 같은 소수 출력
2&3&5&7

풀이

CONNECT BY LEVEL 구문으로 2이상 1000 이하의 ROW를 생성하고, WITH절을 사용하여 임시 테이블로 만들어 줍니다.

NOT EXISTS 조건으로 약수 여부를 확인해서 제외합니다.

결과를 한 줄로 표시하기 위해 LISTAGG 함수를 활용했습니다.

LISTAGG 함수 기본 사용법 (Oracle 11g 이상)
LISTAGG(컬럼명, '구분기호') WITHIN GROUP(ORDER BY 정렬 기준 컬럼)

WITH NUMBERS AS (
  SELECT LEVEL NUM
    FROM DUAL
   WHERE LEVEL > 1
   CONNECT BY LEVEL <= 1000
)
SELECT LISTAGG(N.NUM, '&') WITHIN GROUP(ORDER BY N.NUM)
  FROM NUMBERS N
 WHERE NOT EXISTS (SELECT NUM
                     FROM NUMBERS E
                    WHERE E.NUM < N.NUM
                      AND MOD(N.NUM, E.NUM) = 0
                  )

 

여기서 나누는 값의 범위를 제곱근(SQRT) 이하로 줄여도 동일한 결과값을 얻을 수 있습니다.

• E.NUM < N.NUM  ☞  E.NUM <= SQRT(N.NUM)

약수는 제곱근 값을 기준으로 대칭이기 때문에, 제곱근 값보다 작거나 같은 수로만 나누어지면 그 이상의 숫자로는 계산할 필요가 없기 때문입니다.

예시) 12의 약수는 1, 2, 3, 4, 6, 12
1 * 12, 2 * 6, 3 * 4 < √12 < 4 * 3, 6 * 2, 18

WITH NUMBERS AS (
  SELECT LEVEL NUM
    FROM DUAL
   WHERE LEVEL > 1
   CONNECT BY LEVEL <= 1000
)
SELECT LISTAGG(N.NUM, '&') WITHIN GROUP(ORDER BY N.NUM)
  FROM NUMBERS N
 WHERE NOT EXISTS (SELECT NUM
                     FROM NUMBERS E
                    WHERE E.NUM <= SQRT(N.NUM)
                      AND MOD(N.NUM, E.NUM) = 0
                  )
;

결과