Print Prime Numbers (소수 구하기) feat. 재귀함수

Q : Write a query to print all prime numbers less than or equal to 1000 . Print your result on a single line, and use the ampersand ( & ) character as your separator (instead of a space).

For example, the output for all prime numbers  <= 10

would be: 2&3&5&7

문제 : 1000 과 같거나 작은 모든 소수를 출력하는 쿼리문을 작성하시오. 한 줄에 출력하되 숫자간 구분은 문자 '&' 을 사용하시오. 예를 들어 10보다 작은 소수를 출력하면 2&3&5&7 이 출력되어야 합니다.

 

간단히 재귀 함수를 떠올려서 이를 쿼리문으로 바꾸면 된다.

1차적으로 1000까지의 숫자를 생성하는 함수

2차적으로 소수를 선택하는 함수

3차적으로 선택된 소수를 정해진 문자로 구분하여 출력하는 함수

작동 방식

초기 테이블 세팅
PrimeNumbers
------------
| num      |
------------
| 2        |
------------

숫자 생성하기
PrimeNumbers
------------
| num      |
------------
| 2        |
| 3        |
| 4        |
| ...      |
| 1000     |
------------

소수 골라내기
OnlyPrimes
------------
| num      |
------------
| 2        |
| 3        |
| 5        |
| 7        |
| ...      |
| 997      |
------------​

코드 구현

/* 재귀적으로 소수를 찾기 위한 함수 정의 */
WITH RECURSIVE PrimeNumbers AS (
    /* 초기 값으로 2를 선택 */
    SELECT 2 AS num
    UNION ALL
    /* num 값을 1씩 증가시키며 1000 이하의 숫자를 생성 */
    SELECT num + 1
    FROM PrimeNumbers
    WHERE num + 1 <= 1000
),

/* 생성된 숫자 중 소수만 선택하기 위한 함수 */
OnlyPrimes AS (
    /* PrimeNumbers에서 숫자를 선택 */
    SELECT num
    FROM PrimeNumbers p1
    /* 현재 숫자보다 작은 숫자 중 나누어 떨어지는 숫자가 없을 때만 선택 */
    WHERE NOT EXISTS (
        SELECT 1
        FROM PrimeNumbers p2
        WHERE p2.num < p1.num
        AND p1.num % p2.num = 0
    )
)

/* 소수들을 '&'로 구분하여 하나의 문자열로 출력 */
SELECT GROUP_CONCAT(num SEPARATOR '&') AS Primes
FROM OnlyPrimes;