Lv.0 소인수분해

송민혁·2023년 4월 4일

coding test 코딩테스트 프로그래머스

Coding Test

목록 보기

9/15

문제

분석

소인수분해란 어떤 수를 소수(prime number)들의 곱으로 표현하는 것이다.

소수이면서 주어진 수의 약수이면 된다.

소수 => 소수 판별식
주어진 수의 약수 => filter

소수 판별

일반적인 방법) 소수 판별하기

소수(prime number)란 1과 자기 자신의 수로만 나눌 수 있는 수이다. 즉 1과 자기 자신을 제외하고는 약수가 없어야 한다.

function isPrime(num) {
    if (num === 1) {
        return false;
    } else if (num === 2) {
        return true;
    } else {
        for (let i = 2; i < num; i++) {
            if (num % i === 0) { 
                return false;
            }
        }
        return true;
    }
}

제곱근을 이용하여 소수 판별하기

만약 어떤 수 N의 제곱근보다 작은 수에서 약수가 존재하지 않는다면, N의 제곱근보다 큰 수에서도 약수가 존재하지 않는다.

따라서 어떤 수 N을 2, 3, ..., N의 제곱근으로 나눴을 때 모두 나누어 떨어지지 않으면 N은 소수이다. 위의 소수 판별 방식보다 for문 반복 횟수가 줄어든다.

function isPrime(N) {
  // 1은 소수가 아니다.
  if (N === 1) return false;
  // 2부터 N제곱근까지의 수로 N을 나눴을 때
  for (let i = 2; i <= Math.sqrt(N); i++) {
    // 나누어 떨어지는 경우가 한 번이라도 있으면 N은 소수가 아니다.
    if (N % i === 0) return false;
  }
  // 모두 나누어 떨어지지 않으면 N은 소수이다.
  return true;
}

코드 구현

모범 답안

while 조건식에는 소수의 조건을 넣고
n은 i로 나눈 후의 값이 되어야 하고

new Set()은 나눈 후에 중복된 값을 없애기 위해서 사용한다.

ChatGPT
자바스크립트에서 Set은 중복을 허용하지 않는 값의 컬렉션을 나타내는 자료구조입니다. Set 객체를 생성하려면 new 키워드와 함께 Set() 생성자를 호출하면 됩니다.

예를 들어, 다음과 같이 Set을 생성하고 값을 추가할 수 있습니다.

Copy code
// Set 생성
const mySet = new Set();

// 값 추가
mySet.add(1);
mySet.add(2);
mySet.add(3);

console.log(mySet); // Set(3) { 1, 2, 3 }

// 또한, Set 객체는 이터러블(iterable)한 객체를 받아들일 수 있습니다. 예를 들어, 배열을 Set으로 변환할 수 있습니다.

javascript
Copy code
const myArray = [1, 2, 2, 3, 3, 3];
const mySet = new Set(myArray);

console.log(mySet); // Set(3) { 1, 2, 3 }

위의 예제에서, 중복된 값이 제거되어 Set에는 [1, 2, 3]만 포함되게 됩니다.

Set 객체의 메소드로는 add, delete, has, clear 등이 있습니다. 자세한 내용은 자바스크립트 공식 문서에서 확인하실 수 있습니다.