문제

Print Prime Numbers
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).

아직도 이걸 왜 SQL 문제로 냈는지는 모르겠지만
1부터 1000까지의 수 중 소수를 찾고, 이를 '&'를 구분자로 하여 1개의 row로 반환하는 문제

SQL

풀이 과정

소수의 개념을 기반으로 풀이를 진행해야 한다
소수는 '1과 자기 자신으로만 나누어 떨어지는 수'인데,
이를 반대로 말하면 '1과 n 이외에 나누었을 때 나머지가 0인 경우 d(자연수)가 있는 자연수 n'을 구하는 문제가 된다

즉, 아래와 같은 순서로 문제를 풀게 된다
(1) 2부터 n까지 전체 숫자가 포함된 테이블 생성
(2) 해당 테이블을 Self Join하여 나머지 구하기
(3) 소수만 필터링: 나머지가 0인 경우의 count(*)값이 2 미만인 경우만 뽑아내기
(4) 문자열을 구분자 '&'로 합치기

(1) dim_number Table 생성

재귀 함수를 통하여 2부터 n까지의 수를 갖고 있는 테이블을 생성한다.
일단은 @max = 11인 케이스로 코드를 작성하고, 마지막에 숫자만 1,000으로 바꿔줄 예정

WITH recursive dim_numbers(n) AS (
    SELECT
        2 as "n"
    UNION ALL
    SELECT
        n + 1 as "n"
    FROM
        dim_numbers
    WHERE
        n < 11
)
SELECT
    *
FROM
    dim_numbers
;

(2) 나머지 구하기: Self Join

dim_numbers를 각각 나누어지는 수(divided), 나누는 수(divisor)로 나누어 Self Join을 실행한다
이 때, 나누는 수는 나누어지는 수보다 클 수 없으므로 ON절에 조건을 걸어주었다

WITH recursive dim_numbers(n) AS (
    SELECT
        2 as "n"
    UNION ALL
    SELECT
        n + 1 as "n"
    FROM
        dim_numbers
    WHERE
        n < 11
),
is_prime(divided, divisor) AS (
    SELECT
        n.n as "n"
        , d.n as "d"
    FROM
        dim_numbers n
        INNER JOIN dim_numbers d ON n.n >= d.n
    ORDER BY
        n, d
)
SELECT
    *
FROM
    is_prime
;

(3) 소수 필터링

1번 컬럼이 나누어지는 수, 2번 컬럼이 나누는 수
만약 소수라면 나머지가 0인 경우가 1번만 나와야 한다 (1은 제외하고 보고 있으므로)

WITH recursive dim_numbers(n) AS (
    SELECT
        2 as "n"
    UNION ALL
    SELECT
        n + 1 as "n"
    FROM
        dim_numbers
    WHERE
        n < 11
),
is_prime(divided, divisor) AS (
    SELECT
        n.n as "n"
        , d.n as "d"
    FROM
        dim_numbers n
        INNER JOIN dim_numbers d ON n.n >= d.n
    ORDER BY
        n, d
)
SELECT
    divided
FROM
    is_prime
WHERE
    divided % divisor = 0
;

나머지=0인 경우가 1개인 경우만 남기면 소수만 구할 수 있게 된다

WITH recursive dim_numbers(n) AS (
    SELECT
        2 as "n"
    UNION ALL
    SELECT
        n + 1 as "n"
    FROM
        dim_numbers
    WHERE
        n < 11
),
is_prime(divided, divisor) AS (
    SELECT
        n.n as "n"
        , d.n as "d"
    FROM
        dim_numbers n
        INNER JOIN dim_numbers d ON n.n >= d.n
    ORDER BY
        n, d
)
SELECT
    divided
FROM
    is_prime
WHERE
    divided % divisor = 0
GROUP BY
    divided
HAVING
    count(*) < 2
;

(4) 문자열 합치기

방금 구한 값을 GROUP_CONCAT로 묶어주면 끝난다
이 때 SEPARATOR만 '&'로 지정해주도록 하자

WITH recursive dim_numbers(n) AS (
    SELECT
        2 as "n"
    UNION ALL
    SELECT
        n + 1 as "n"
    FROM
        dim_numbers
    WHERE
        n < 11
),
is_prime(divided, divisor) AS (
    SELECT
        n.n as "n"
        , d.n as "d"
    FROM
        dim_numbers n
        INNER JOIN dim_numbers d ON n.n >= d.n
    ORDER BY
        n, d
),
find_prime_numbers(prime_num) AS (
    SELECT
        divided
    FROM
        is_prime
    WHERE
        divided % divisor = 0
    GROUP BY
        divided
    HAVING
        count(*) < 2
)
SELECT
    GROUP_CONCAT(prime_num SEPARATOR '&') as "prime_numbers"
FROM
    find_prime_numbers
;

여담으로 여기서 CTE 한 번 덜 쓰겠다고 find_prime_numbers에서 그대로 GROUP_CONCAT을 하면 문제에서 요구하는 대로 1개 row가 아니라 기존에 나왔던 것처럼 여러 개의 rows가 나오게 된다
GROUP BY가 먼저 수행되어서 소수인 케이스를 남길 때 devided마다 1개 row가 생기는데, GROUP_CONCAT은 각 row마다 한 번씩 작동하기 때문

마지막으로 테스트를 위해 11로 조정해두었던 값을 1000으로 바꿔주면 끝난다

WITH recursive dim_numbers(n) AS (
    SELECT
        2 as "n"
    UNION ALL
    SELECT
        n + 1 as "n"
    FROM
        dim_numbers
    WHERE
        n < 1000
),
is_prime(divided, divisor) AS (
    SELECT
        n.n as "n"
        , d.n as "d"
    FROM
        dim_numbers n
        INNER JOIN dim_numbers d ON n.n >= d.n
    ORDER BY
        n, d
),
find_prime_numbers(prime_num) AS (
    SELECT
        divided
    FROM
        is_prime
    WHERE
        divided % divisor = 0
    GROUP BY
        divided
    HAVING
        count(*) < 2
)
SELECT
    GROUP_CONCAT(prime_num SEPARATOR '&') as "prime_numbers"
FROM
    find_prime_numbers
;

핵심 포인트

약수의 개수를 구하기 위해 dim_table을 만들고, 이를 Self Join한다는 아이디어를 떠올릴 수 있다면, 나머지는 그래도 수월한 문제였다
Self Join을 할 때도, ON절 조건을 통해서 divisor가 divided보다 작거나 같다는 조건을 걸어준다면, 나머지를 계산하기에 필요한 값을 모두 구할 수 있다.

Python

풀이 과정

Python은 SQL과 다르게 리스트를 활용해 값을 저장할 수 있으므로, 같은 방식이라면 보다 쉽게 접근할 수 있다
2부터 n까지의 수 i를 for문을 통해 돌리면서
기존의 prime_num 값으로 나누어 떨어지지 않는 수만을 취하면 된다
또한, 소수는 기본적으로 2~n의 제곱근 까지만 확인해보면 되므로 연산량도 줄일 수 있다

import math

prime_list = []
for i in range(2, 1000+1):
    is_prime = True
    for n in prime_list:
        if n > math.sqrt(i):
            break        
        elif i % n == 0:
            is_prime = False
            break
        else:
            pass
    if is_prime:
        prime_list.append(i)

for num in prime_list:
    print(num, end='&')

GPT의 코드 튜닝

이걸 GPT가 한 번 더 개선해주니 아래와 같아졌다
부동 소수점 계산인 math.sqrt보다 정수 제곱근을 반환하는 math.isqrt가 반복 조건에 더 적합하다...고 하고 (이 부분은 그러려니 넘어갔다)
print에 end 파라미터를 넣기보다 join()을 통해 하나의 문자열로 합하고 한 번에 출력함으로써 출력 성능을 향상시킬 수 있다

import math

prime_list = []

for i in range(2, 1000+1):
    is_prime = True
    sqrt_i = math.isqrt(i)
    for n in prime_list:
        if n > sqrt_i:
            break
        if i % n == 0:
            is_prime = False
            break
    if is_prime:
        prime_list.append(i)

print('&'.join(map(str, prime_list)))

에라토스테네스의 체 방식

여기서 보다 성능을 높이려면, 루프 방식 대신 아래와 같이 구현할 수 있다...고 한다

에라토스테네스의 체 방식이란,
2부터 시작해서, 해당 수의 배수들을 모두 지운다.
그리고 그 다음 남은 수를 기준으로 또 그 배수들을 지운다.
이걸 반복하면 남는 수는 모두 소수다.

is_prime을 0부터 limit까지 True인 리스트로 만든 뒤,
0, 1을 False로 바꾸고
2부터 limit의 제곱근까지의 수를 i로 for문을 돌리면서
그 때 그 때 해당 i를 제외한 i의 배수를 전부 False로 바꿔버리는 방식이다

limit = 10000000
is_prime = [True] * (limit + 1)
is_prime[0] = is_prime[1] = False

for i in range(2, int(limit**0.5) + 1):
    if is_prime[i]:
        for j in range(i*i, limit+1, i):
            is_prime[j] = False

prime_list = [i for i, val in enumerate(is_prime) if val]
print('&'.join(map(str, prime_list)))

limit=10,000,000 기준, 34.0s -> 2.5s로 비약적인 성능 향상이 나타난다

사람들 진짜 똑똑하다...