문제 설명

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

제한사항

1 ≤ n ≤ 100

입출력 예

n	result
10	5
15	8

입출력 예 설명

입출력 예 #1

10 이하 합성수는 4, 6, 8, 9, 10 로 5개입니다. 따라서 5를 return합니다.

입출력 예 #2

15 이하 합성수는 4, 6, 8, 9, 10, 12, 14, 15 로 8개입니다. 따라서 8을 return합니다.

문제 해결방안 1

function isComposite(number) {
  // 1과 자기 자신을 제외한 약수가 하나라도 있는지 확인
  for (let i = 2; i < number; i++) {
    if (number % i === 0) {
      // 나누어떨어지면 합성수
      return true
    }
  }
  // 나누어떨어지는 약수가 없으면 합성수가 아님
  return false
}

function solution(n) {
  let count = 0
  // 가장 작은 합성수는 4에서 n까지 모든 숫자에 대해 합성수인지 확인
  for (let i = 4; i <= n; i++) {
    if (isComposite(i)) {
      count++
    }
  }
  return count
}

문제 해결방안 2

function isComposite(number) {
  for (let i = 2; i <= Math.sqrt(number); i++) {
    if (number % i === 0) {
      return true
    }
  }
  return false
}

function solution(n) {
  let count = 0

  for (let i = 4; i <= n; i++) {
    if (isComposite(i)) {
      count++
    }
  }

  return count
}

알게된 점 💡

합성수: 1과 자기 자신 이외에 다른 자연수로도 나눌 수 있는 1보다 큰 자연수를 말합니다. 다시 말해, 최소한 하나 이상의 다른 자연수 약수를 가지고 있는 수죠. 따라서 1과 자기 자신이 아닌 수로 나누어 떨어지면 합성수입니다!
가장 작은 합성수: 4
- 1은 합성수가 아닙니다. 왜냐하면 약수가 1밖에 없기 때문입니다.
- 2와 3은 소수(prime number)입니다. 소수는 1과 자기 자신만을 약수로 가지는 숫자이므로, 합성수가 아닙니다.
- 4는 1, 2, 4를 약수로 가집니다. 1과 자기 자신을 제외한 2라는 약수가 있기 때문에, 4는 첫 번째 합성수입니다.
composite: 합성수
Math.sqrt: 제곱근(square root)을 계산하는 메서드
- Math.sqrt(9)는 3을 반환
제곱근을 넘어가는 수까지 확인할 필요가 없기 때문에 계산 시간을 줄일 수 있습니다.
- 제곱근보다 큰 수로 나누었을 때 나오는 다른 수는 반드시 제곱근보다 작습니다. 예를 들어, 16을 5로 나누면 3.2가 됩니다. 5는 제곱근 4보다 크고, 3.2는 4보다 작죠. 따라서, 제곱근보다 작은 수로 나누어지지 않는다면, 제곱근보다 큰 수로도 나누어지지 않습니다. 이렇게 제곱근까지만 확인함으로써 계산을 더 효율적으로 할 수 있습니다. 간단히 말해서, 어떤 수가 합성수인지 확인하려면 그 수의 제곱근까지만 나눠보면 됩니다. 제곱근을 넘어가는 수까지 나눠볼 필요가 없어서, 계산 시간을 줄일 수 있는 것입니다.

느낀점 💭

수포자라서 공부가 많이 필요한 것 같다
수학관련 문제는 다시 한번 더 복습하고 여러번 풀어보자.

References

합성수 찾기