소수(Prime Number)구하기 - Javascript

문제

정수를 입력받아 2부터 해당 수(num)까지의 소수들을 문자열로 리턴

• string 타입, '2-3-5-7'의 형식
• 이중 반복문(for문)을 사용할 것

풀이

우선 소수의 정의부터 명확히 하면, 소수(Prime Number)란 '양의 약수가 1과 자기 자신 뿐인, 1보다 큰 자연수'이다.  예를 들어, 5는 1×5 또는 5×1로 수를 곱한 결과를 적는 유일한 방법이 자신을 포함하기 때문에 소수라고 할 수 있다.

 

ver1

이중 반복문을 사용해야한다는 조건이 있어서, 우선 첫번째 for문을 어떤식으로 구성할 지 생각해봤다.

 

    1. 입력되는 수(num)가 2이상이기 때문에, 모든 결과값에 포함될 2를 출력 문자열(result)에 2를 미리 지정해둔다. 

    2. 3부터 num까지 반복문을 통해 하나씩 소수인지 확인한다.

    3. 만약 소수라면 출력 문자열(result)에 추가한다.

    4. 출력 문자열(result)을 return한다.

 

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

  for(let i=3; i<=num; i++){
   
    // 소수인지 판별하는 코드
    
    if (소수가 맞다면){
      result += `-${i}`
    }
  }
  return result;
}

 

그리고 두번째 for문으로 들어갈 '소수인지 판별하는 코드'를 추가했다.

    1. 소수 여부를 뜻하는 isPrime을 선언한다.

    2. 해당 수(i)를 2부터 해당 숫자-1(i-1)까지 나눌 때, 하나도 나누어지지 않는다면 소수로 판단한다.

       = 본인(i)외에 약수가 존재하지 않음

    2. isPrime의 기본값을 true로 두고,

    3. 2번의 조건을 어기는 즉시 false 반환 + break (반복문 종료)

 

이렇게 두 반복문을 합친 코드이다.

 

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

  for(let i=3; i<=num; i++){
  
    //소수인지 판별하는 코드
    let isPrime = true;
    for(let j=2; j<i; j++){
      if(i%j===0){
        isPrime = false;
        break;
      }
    }
    
    if (isPrime === true){
      result += `-${i}`
    }
  }
  return result;
}

 

ver2

우선 기본적인 이중 반복문의 틀을 잡고나니 반복횟수를 좀 더 줄일 방법은 없는 지 고민이 되기 시작했다.

최대한 반복문이 돌아가는 횟수를 줄여보고자 다음 두 가지 조건을 추가해서 코드를 개선했다.

 

    1. 짝수는 무조건 2를 약수로 갖기 때문에 소수에서 가차없이 제외해도 된다.

    2. 어떤 수(N)의 약수가 존재한다면 다른 약수와 짝지어지기 때문에, 제곱근(sqrt(N))의 범위까지만 판단해도 충분하다.

          ex. N=12 이면 약수는 1*12, 2*6, 3*4 형태로 존재한다. 여기서 1,2,3만 알면 나머지는 알아서 정해진다.

               그렇기 때문에 어떤 두 수를 곱해서 최대 N이 되는 지점까지만 판별하면 된다. 이 지점이 바로 제곱근(sqrt(N))이다.

 

이 두 조건을 ver1 코드에 추가하기 위해

 

    1. 첫번째 for문의 증감문을 i++에서 i+=2로 변경했다.

       - 초기값이 3이기 때문에 3,5,7... 홀수만 확인이 가능하다.

    2. 두번째 for문의 조건 범위를 i 대신 i의 제곱근으로 변경했다.

 

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

  for(let i=3; i<=num; i+=2){
    let isPrime = true;
    for(let j=2; j<=Math.sqrt(i); j++){
      if(i%j===0){
        isPrime = false;
        break;
      }
    }
    if (isPrime === true){
      result += `-${i}`
    }
  }
  return result;
}