코플릿 / 반복문(소수찾기+제곱근)

support·2021년 9월 1일

코테

코딩테스트

목록 보기

7/11

문제

1 이상의 자연수를 입력받아 소수(prime number)인지 여부를 리턴해야 합니다.

입력

인자 1 : num

number 타입의 수

출력

boolean 타입을 리턴해야 합니다.

입출력 예시

let output = Prime(2);
console.log(output); // --> true

output = Prime(6);
console.log(output); // --> false

output = Prime(17);
console.log(output); // --> true

힌트

자바스크립트 내장 객체인 Math를 활용해 불필요한 연산을 줄일 수 있습니다. (javascript square root 또는 자바스크립트 제곱근)

해설

소수는 약수의 개수가 2개 뿐인 수,  1과 자기 자신으로만 나누어 떨어지는 수를 말한다

function Prime(num) {
  // 예외적 숫자를 먼저 처리해 주자
  // 모든 짝수는 2의 배수이기 때문에 소수가 아니다 
  // 하지만 2는 1과 자기 자신인 2로 나누어 떨어지는 약수가 2개인 수이기 때문에 소수다
  if(num === 2){
    return true;
  }
  
  // 1은 1과 자기자신으로 나누어떨어지긴 하지만, (1 % 1 === 0)
  // 약수의 개수가 하나뿐이라서 소수가 아니다 (2개여야 한다)
  if(num === 1){
    return false;
  }
  // 2의  배수도  소수가 아니므로 false를 리턴해준다
  if (num % 2 === 0){
    return false;
  }
  // 1과 2는 이미 지정을 해줬으니 3부터 시작하면 된다
  // 2의 배수를 제외해서 홀수만 체크해도 되니 i에 2씩 더해준다
  for(let i = 3; i < num; i+=2){
    	// 이제 i의 값은 1도 num 자기자신도 아닌 홀수들로 구성되어있다
	// num을 i로 나눴을 때 나머지가 0이면, 1과 자기자신 외에도 
        //i를 약수로 갖는 숫자가 되므로 false를 리턴해준다
    if(num % i === 0){
      return false;
    }
  }
  return true;
  // 반복문을 지나서 true인 수는 1과 자기자신으로만 나누어떨어지는 숫자이므로 소수다 
}

제곱근 사용 해설

힌트에서 제곱근을 사용하라고 하는데 제곱근을 사용해서 어떻게 문제를 풀 수 있는지 보자

function Prime(num) {
  // Math.sqrt()는 입력값의 제곱근을 구한다 
  // ex) Math.sqrt(4) === 2, Math.sqrt(81) === 9
  // parseInt는 입력값의 소수점을 떼어내고 정수로 만들어준다
  // Math.floor()과 비슷하다

let sqrt = parseInt(Math.sqrt(num));

if ( num === 1 ){
  return false;
}

if (num === 2){
  return true;
}

if (num % 2 === 0){
  return false;
}
// for문의 조건문에서 차이가 있다 ( 이전 : i <= num / 이후 : i < sqrt )
for (let i = 3; i <= sqrt; i += 2) {  
    if (num % i === 0) {
     return false;
    }
  }
  return true;
}