HackerRank SQL - 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).

For example, the output for all prime numbers  would be:

2&3&5&7

Problem

1~1000 중 소수를 출력하되, &문자로 구분하여 하나의 행으로 출력하라.

---

Answer1

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

값이 제공되는 테이블이 별도로 주어지지 않기 때문에, 임시테이블을 생성하고 여기에 소수를 판별하는 쿼리를 작성하면 된다. 

---

How to solve

우선 1~1000까지 숫자를 출력하는 WITH절의 임시 테이블을 만들어준다..

어차피 1은 소수가 아니니, 2부터 시작한다.

WITH RECURSIVE numbers AS (
  SELECT 2 AS n
  UNION ALL
  SELECT 1+n FROM numbers WHERE n<1000
)

 

다음, 소수를 찾아야 한다.

소수를 찾는 공식은 (아직까지) 존재하지 않는다. 그러나 어떤 수가 소수인지 아닌지는 알 수 있다. 따라서 해당 문제에서는 소수가 아닌 수를 제외하여 추출하면 된다.

소수의 정의는 1과 자기 자신으로 밖에 나누어 떨어지지 않는 1 이외의 정수, 양의 약수가 2개인 수를 의미한다.

 

만들어둔 임시테이블 다시 가지고 와서 중첩테이블을 만들어준다.

n2 테이블의 n이 numbers 테이블의 n보다 크면서 나누었을 때, 나머지가 존재하지 않는 수가 존재한다면, 이건 소수가 아니라고 할 수 있다. 여기서 numbers의 n값을 제곱근 이하로 비교한 이유는 약수는 제곱근 값을 기준으로 대칭이기 때문에  제곱근 이상은 비교할 필요가 없기 때문이다. 당연히 시간이나 비용적인 측면에서도 좀 더 효율적인 쿼리가 된다.

SELECT n
FROM numbers
WHERE NOT EXISTS(SELECT n2.n #소수가 아닌 수 제외
                   FROM numbers AS n2
                  WHERE n2.n > 1 
                    AND n2.n <= SQRT(numbers.n)
                    AND numbers.n % n2.n = 0)

 

 

마지막으로 위의 쿼리도 임시테이블로 묶어서 메인 쿼리로 넘겨주면 된다.

이 때, group_concat이라는 함수를 사용했는데, 행으로 이루어진 값을 모두 합쳐주는 함수다. 

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

평소에는 수학을 쓸 일이 없지만, 이런 문제를 풀 때 찾아보면 꽤 재밌는 것 같다.

아무튼 풀다보니 항상 하던 방식으로만 접근하는 것도 좋은 것 같진 않다는 생각이 든다.

 

 

참고 자료

• https://yurimyurim.tistory.com/16