[알고리즘-프로그래머스] 합성수 찾기

합성수란 ?

1과 자기 사진 이외의 양의 약수를 가지는 자연수

 

[어떻게 풀것인가?]

1. 1부터 n까지 자연수 하나씩 확인 (1,2,3은 합성수가 아니기에 미리 제외하고 반목문 돌리기)

2. 각 자연수에 대해 약수 찾기

3. 약수가 1과 자기자신 외에 수가 있다면 그 수는 합성수

 

[코드]

public int solution(int n) {
    int answer = 0;
    int cnt = 0;

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