알고리즘: 2부터 주어진 수까지의 소수 구하기 [2/22]

어제 두세 시간을 생각해도 풀지 못했던 알고리즘 문제를 오늘은 10분만에 해결했다. 어젯밤에 소수를 판별하는 함수를 만든 것이 도움이 된 것 같다.

이 문제는 2부터 주어진 수까지의 소수를 구해야 한다.
listPrimes(5)를 실행하면 2, 3, 5가 리턴되고
listPrimes(15)를 실행하면 2, 3, 5, 7, 11, 13이 리턴되는 식이다.

의사 코드

이를 위해 작성한 의사 코드는 다음과 같다.

1. 외부 for문으로 target 숫자를 고정한다.
2. 내부 for문으로 target 숫자를 2부터 target 숫자 -1(자기 자신 바로 전)까지 나눈다.
3. 만약 내부 for문을 작동시키는 과정에서 나누어 떨어지는 수가 있다면 그 target 숫자에 대한 for문 동작을 정지시키고, 다음 target 숫자로 넘어간다. (즉, 내부 for문을 중단시키고 외부 for문으로 돌아간다)
4. 만약 target 숫자 -1(자기 자신 바로 직전 숫자)까지 나누었는데도 불구하고 한 번도 나누어 떨어진 적이 없다면 소수이므로 result에 넣는다.

작성한 코드

function listPrimes(num) {
  let result = "2";

  for (let target = 2; target <= num; target++) {
    for (let i = 2; i < target; i++) { // 1을 제외한 수부터(2부터) 자기 자신 전까지 나누어보는 수
      if (target % i === 0) {
        break;
      }

      if (i === target - 1) {
        result = `${result}-${target}`;
      }
    }
  }

  return result;
}