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

문제 설명

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

제한사항

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합니다.

풀이

합성수로만 이뤄진 배열을 빈 배열로 초기화하고,
합성수의 개수를 세기 위한 변수(cnt)를 초기화한다.

약수가 세 개 이상인 수가 합성수이므로,
n이 주어졌을 떄 n 이하의 수를 하나씩 꺼내서 그 수의 약수가 세 개 이상인지 확인해야 한다.
이때, n 이하의 수의 범위는 4부터 시작한다. (1, 2, 3의 약수는 3개가 될 수 없으므로)

따라서 중첩 반복문이 필요하다. (n 이하의 수 i가 있고, i 이하의 수인 j를 또 나눠서 약수인지 확인해야 하기 때문)

j의 범위는 1부터 시작해서 i까지로 지정한다. (자기 자신도 약수에 포함되기 때문)
i를 j로 나눴을 때 0이면 i의 약수 배열에 append(i)로 포함시킨다.

이렇게 해서 약수의 개수가 3 이상이면 그 수는 합성수다.
합성수를 카운트하는 변수 cnt에 1을 더한다.

def solution(n):
    num = []
    cnt = 0
    for i in range(4, n+1):
        for j in range(1, i+1):
            if i % j == 0:
                num.append(i)
        if num.count(i) >= 3:
            cnt += 1
    return cnt