Print Prime Numbers

문제

Write a query to print all prime numbers less than or equal to . 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:

1000 보다 작거나 같은 모든 소수를 인쇄하는 쿼리를 작성합니다. 결과를 한 줄에 인쇄하고 공백 대신 앰퍼샌드(&) 문자를 구분 기호로 사용합니다.

WITH RECURSIVE numbers AS(
    SELECT 2 as n
    UNION ALL
    SELECT n + 1 FROM numbers WHERE n + 1 < 1000
), is_prime AS (
    SELECT n.n,
    NOT EXISTS(
        SELECT 1
        FROM numbers d
        WHERE d.n < n.n AND d.n > 1 AND n.n % d.n = 0
    ) AS prime
    FROM numbers n 
)
SELECT GROUP_CONCAT(n SEPARATOR '&') AS primes
FROM is_prime
WHERE prime = TRUE;

매우 어려웠다. DELIMITER 라는 함수도 있던데 내일은 이걸 공부 해 봐야겠다. 여기서 반복문 조건문 등 실제 코드처럼 짤 수 있는 거 같다.

위 코드 작동방식은 아래와 같다.

1. 첫번째 재귀에서 2부터 1000까지 구한다

2. 두번째 NOT EXISTS는 True or False를 구하는 식이다. 여기서도 첫번째 재귀를 호출하는데

d.n이 n.n보다 작고 (n.n은 소수인지 아닌지 판별하기 위한 수, 당연히 d.n이 작아야 한다), d.n이 1보다 크다. n.n % d.n은 보다 자세하게 설명한다.

n.n이 7이면 d.n은 2 부터 6까지가 된다. 이 수들을 n.n에 하나하나 나눠 본다. NOT EXISTS는 어떤 행도 반환하지 않을때 TRUE이고 행 하나라도 반환하면 FALSE이다. 

7 % 2, 7 % 3, 7 % 4, 7 % 5, 7 % 6 결과는 모두 나누어 떨어지지 않으므로 행을 반환하지 않는다. 그래서 7인경우는 TRUE. 이런식으로 작업을 한다.

사실 어렵다. 이문제. Hacker Rank가 프로그래머스보다 난이도는 있어 보인다.

<2025년 5월 6일 복습>

WITH RECURSIVE numbers AS(
    SELECT 2 AS n
    UNION ALL
    SELECT 1 + n FROM numbers WHERE n < 1000
),
is_prime AS(
    SELECT n
    FROM numbers
    WHERE NOT EXISTS (
        SELECT n
        FROM numbers n2
        WHERE n2.n > 1 AND
              n2.n <= SQRT(numbers.n) AND
             numbers.n % n2.n = 0
    )
)
SELECT GROUP_CONCAT(is_prime.n ORDER BY is_prime.n SEPARATOR '&') AS PrimeList
FROM is_prime

 여전히 어렵다!