문제 설명

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

class Solution {
    public int solution(int n) {
        int answer = 0;
        return answer;
    }
}

제한 사항

• 1 ≤ n ≤ 100

입출력 예

입출력 예 설명

• 입출력 예 #1

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

• 입출력 예 #1

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

---

해결법

방법 1

class Solution {
    public int solution(int n) {
        int answer = 0;        
        
        // n 이하의 수를 for문으로 돌리기
        for (int i = 1; i <= n; i++) {
            int count = 0;		// 약수 개당 count하기
            
            // 각각의 n 이하의 수 내부를 for문으로 돌리기
            for (int j = 1; j <= i; j++) {
                if (i % j == 0) {		// 나누어떨어질 경우, 약수다.
                    count++;
                }
            }    
            
            // 약수가 3개 이상일 경우, 구하고자하는 조건을 만족하므로 answer에 더한다.
            if (count >= 3) {
                answer++;    
            }
        }
        
        return answer;
    }
}

• 중첩 for문 사용

• if (count >= 3) 조건문이 내부 for문과 외부 for문 중 어디에 있어야할지 주의.

방법 2

class Solution {
    public int solution(int n) {
        int answer = 0;

        for (int i = 4; i <= n; i++) {
            for (int j = 2; j < i; j++) {
                if (i % j == 0) {
                    answer++;
                    break;
                }
            }
        }
        
        return answer;
    }
}

• 합성수에 한정해서 구하는 것이므로
  i의 초기값을 i = 4, j의 초기값을 j = 2 으로 설정할 수도 있다.

---

합성수 찾기