프로그래머스 LV.0 합성수 찾기

프로그래머스 LV.0 합성수 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/120846

프로그래머스

 

1. 문제 명

합성수 찾기

2. 문제 설명

약수의 개수가 세 개 이상인 수를 합성수라고 합니다. 자연수 n이 매개변수로 주어질 때 n이하의 합성수의 개수를 return하도록 solution 함수를 완성해주세요.

3. 제한 사항

- 1 ≤ n ≤ 100

4. 예시

n	result
10	5
15	8

5. 기본 제공 코드

function solution(n) {
    var answer = 0;
    return answer;
}

6. 제출한 내 답

const solution = (n) => {
  let answer = 0;
  for (i = 4; i <= n; i++) {
    for (j = 2; j <= Math.sqrt(i); j++) {
      if (i % j === 0) {
        answer += 1;
        break;
      }
    }
  }

  return answer;
};

 

6-2. VSC에 작성한 내용

const solution = (n) => {
  // 합성수: 약수가 3개 이상인 수
  // 1 <= n <= 100
  let answer = 0;
  // 4부터 n 사이의 수를 확인
  for (i = 4; i <= n; i++) {
    // i를 2부터 i의 제곱근 사이의 수에서 나누어 떨어지는지 확인
    // 모든 약수를 구하는게 아니니까 더 이상은 의미가 없음
    for (j = 2; j <= Math.sqrt(i); j++) {
      if (i % j === 0) {
        answer += 1;
        console.log(i, j);
        break;
      }
    }
  }

  return answer;
};

// 테스트
console.log(solution(10));
console.log(solution(15));
console.log(solution(25));
console.log(solution(49));

7. 특이사항

처음에는 아래와 같이 합성수의 기준을 '정수 n이 2나 3으로 나누어 떨어지는가'로 잡았다.

const solution = (n) => {
  // 합성수: 약수가 3개 이상인 수
  // 1 <= n <= 100
  let answer = 0;
  for (i = n; i > 3; i--) {
    if (i % 2 === 0 || i % 3 === 0) answer += 1;
  }
  return answer;
};

하지만 약수가 1, 7, 49인 49나, 1, 5, 25인 25 같은 경우를 생각하지 않아 채점 과정에서 틀렸다.

 

힌트를 받았는데 합성수를 구할때 '특정 수로 나누어지는가' 보다, '소수가 아닌 수'를 구하는게 좋다고 한다.

이에 따라 2부터 n의 제곱근까지의 수 중 n에서 나누어떨어지는 수가 있는지 검사하는 방법으로 진행했다.

const isPrime = (n) => {
  for (let i = 2; i <= Math.sqrt(n); i++) {
    if (n % i === 0) {
      return false;
    }
  }
  return true;
};

 

8. 다른 사람이 작성한 답

8-1. 하드코딩

function solution(n) {
    if (n === 1) return 0;
    if (n === 2) return 0;
    if (n === 3) return 0;
    if (n === 4) return 1;
    if (n === 5) return 1;
    if (n === 6) return 2;
    if (n === 7) return 2;
    if (n === 8) return 3;
    if (n === 9) return 4;
    if (n === 10) return 5;
    if (n === 11) return 5;
    if (n === 12) return 6;
    if (n === 13) return 6;
    if (n === 14) return 7;
    if (n === 15) return 8;
    if (n === 16) return 9;
    if (n === 17) return 9;
    if (n === 18) return 10;
    if (n === 19) return 10;
    if (n === 20) return 11;
    if (n === 21) return 12;
    if (n === 22) return 13;
    if (n === 23) return 13;
    if (n === 24) return 14;
    if (n === 25) return 15;
    if (n === 26) return 16;
    if (n === 27) return 17;
    if (n === 28) return 18;
    if (n === 29) return 18;
    if (n === 30) return 19;
    if (n === 31) return 19;
    if (n === 32) return 20;
    if (n === 33) return 21;
    if (n === 34) return 22;
    if (n === 35) return 23;
    if (n === 36) return 24;
    if (n === 37) return 24;
    if (n === 38) return 25;
    if (n === 39) return 26;
    if (n === 40) return 27;
    if (n === 41) return 27;
    if (n === 42) return 28;
    if (n === 43) return 28;
    if (n === 44) return 29;
    if (n === 45) return 30;
    if (n === 46) return 31;
    if (n === 47) return 31;
    if (n === 48) return 32;
    if (n === 49) return 33;
    if (n === 50) return 34;
    if (n === 51) return 35;
    if (n === 52) return 36;
    if (n === 53) return 36;
    if (n === 54) return 37;
    if (n === 55) return 38;
    if (n === 56) return 39;
    if (n === 57) return 40;
    if (n === 58) return 41;
    if (n === 59) return 41;
    if (n === 60) return 42;
    if (n === 61) return 42;
    if (n === 62) return 43;
    if (n === 63) return 44;
    if (n === 64) return 45;
    if (n === 65) return 46;
    if (n === 66) return 47;
    if (n === 67) return 47;
    if (n === 68) return 48;
    if (n === 69) return 49;
    if (n === 70) return 50;
    if (n === 71) return 50;
    if (n === 72) return 51;
    if (n === 73) return 51;
    if (n === 74) return 52;
    if (n === 75) return 53;
    if (n === 76) return 54;
    if (n === 77) return 55;
    if (n === 78) return 56;
    if (n === 79) return 56;
    if (n === 80) return 57;
    if (n === 81) return 58;
    if (n === 82) return 59;
    if (n === 83) return 59;
    if (n === 84) return 60;
    if (n === 85) return 61;
    if (n === 86) return 62;
    if (n === 87) return 63;
    if (n === 88) return 64;
    if (n === 89) return 64;
    if (n === 90) return 65;
    if (n === 91) return 66;
    if (n === 92) return 67;
    if (n === 93) return 68;
    if (n === 94) return 69;
    if (n === 95) return 70;
    if (n === 96) return 71;
    if (n === 97) return 71;
    if (n === 98) return 72;
    if (n === 99) return 73;
    if (n === 100) return 74;
    return undefined;
}

 

8-2. Array, fill, map, filter

function solution(n) {
  return Array(n)
    .fill()
    .map((_, i) => i + 1)
    .filter((i) => {
      let cnt = 0;
      for (let j = 1; j <= i; j++) {
        if (i % j === 0) cnt++;
      }
      return cnt >= 3;
    }).length;
}