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

 

 

🔗 합성수 찾기

 

 

문제 설명

약수의 개수가 세 개 이상인 수를 합성수라고 합니다. 자연수 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합니다.

 

 

 

문제 풀이

for문 돌리고 배열에 담아서 약수를 찾아야 할까 고민했는데 분명 내가 번거롭게 생각하고 있을 것이라는 확신이 들어 다시 생각해봤다.

초반에  int count = 0; 를 for문 바깥쪽에 둬서 count가 계속 증가해서 큰 수가 나왔다. 초기화 생각을 못 함;

 

👉 내가 쓴 코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        // 1부터 n까지 순회하면서 각 숫자의 약수 개수를 확인
        for(int i = 1; i <= n; i++){ 
            int count = 0; // 현재 숫자 i의 약수 개수를 저장
            
            // 1부터 i까지 나눠서 i 약수 확인
            for(int j = 1; j <= i; j++){ 
                if(i % j == 0){ // 나머지가 0이면 약수
                    count++;
                } 
            }
            // 약수의 개수가 3개 이상이면 합성수이므로 answer 증가
            if(count >= 3){ 
                answer++;
            } 
        }
        return answer; // 합성수의 개수를 반환
    }
}

 

바깥쪽 for문을 통해 1 ~ n 까지의 수에 대해 반복.

안쪽 for문에서  i에 대해 1부터 j까지 나눠서 약수를 구하고 약수일 경우 count를 증가시킨다.

count가 3개 이상일 경우 answer를 증가시켜주고, 그렇지 않을 경우 다시 for문

 

 

👉 다른 사람 코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        for(int i=4; i<n+1; i++){
            if(i%2==0) {
                answer++; // 4이상 짝수는 전부 합성수
                continue;
            }
            else{
                for(int k=3; k<i/2; k=k+2){
                    if(i%k==0){
                        answer++;
                        break;
                    }
                }
            }
        }
        return answer;
    }
}

 

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를 4부터 시작해서 푸는 방법도 있다.