[프로그래머스] 합성수 찾기

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

---

제한사항

• 1 ≤ n ≤ 100

---

입출력 예

 

n	result
10	5
15	8

---

입출력 예 설명

입출력 예 #1

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

입출력 예 #1

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

 

 

function solution(n) {
  // 약수의 개수가 3개 이상. 
  // 모든 수는 1과 자기 자신을 약수로 갖는다. 
  // 1부터 n까지의 수 중에서 1과 자기 자신이 아닌 수로 나누었을때 0이 되는 수가 하나라도 있다면 그 수는 약수가 3개 이상이다. 
  let count = 0;
  for (let i = 4; i <= n; i++) {
      for (let j = 2; j < i; j++) {
          if (i % j === 0) {
            count += 1;
            break;
          };
        }
  }
  
  return count;
}

 

합성수는 약수의 개수가 3개 이상이다. 

1 이상의 약수는 적어도 1과 자기자신을 약수로 가진다. 따라서 1 이상의 수는 모두 기본적으로 2개의 약수를 가지고 있다. 그렇다면 1부터 n까지의 수 중에서 1과 자기 자신이 아닌 수로 나누었을때 0이 되는 수가 하나라도 있다면 그 수는 약수가 3개 이상임으로 합성수라고 할 수 있다. 

 

총 개수를 담아줄 변수 count를 선언했다. 

반복문 for를 사용해서 i부터 n까지 반복한다. i가 4인 이유는 1, 2, 3은 1과 자기자신만을 약수로 갖기 때문이다. 4부터는 1, 2, 4로 약수가 3개이다. 

그 다음 내부 반복문 for에서는 j를 2부터 시작하고 i 전까지 반복한다. 1과 자기 자신을 제외한 수로 i가 나누어떨어지는지 확인하기 위해서이다. 

만약 i를 j로 나누었을때 나머지가 0이라면, 그 수는 약수가 3개 이상이다. 그러므로 이후의 연산은 반복할 필요가 없음으로 break를 사용해서 빠져나온다. 

 

 

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