합성수 찾기

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

프로그래머스

---

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

---

합성수의 개수를 찾아내는 문제입니다.

합성수를 찾기 위해서는 약수의 개수를 찾아야 하므로, 약수 개수를 찾는 함수를 따로 만들면 편하게 풀 수 있습니다.

다만 이 약수를 찾는 게 정말 효율적인지는 조금 고민해봐야겠네요.

파이썬으로 문제를 풀어보겠습니다.

def cnts(n):
    # 약수의 개수 cnt
    cnt = 0
    # 제곱근까지만 반복
    for i in range(1, int(n ** (1/2)) + 1):
        # 좌우 대칭 관계이므로 2씩 추가
        if n % i == 0:
            cnt += 2
        # 제곱 관계일 경우 1개 삭제
        if i**2 == n:
            cnt -= 1
    return cnt

def solution(n):
    # 약수의 개수가 3개 이상인 값들의 배열로 저장
    # 해당 배열의 길이 = answer
    answer = len([i for i in range(n + 1) if cnts(i) >= 3])
    return answer

이 코드는 엄청 효율적이진 않습니다. 시간 복잡도는 O(n√n) 입니다.

 

에라토스테네스의 체를 조금 응용해서 문제를 더 빠르게 풀 수 있습니다.

def solution(n):
    # n까지 숫자의 약수 개수를 추가합니다.
    divisor_count = [0] * (n + 1)
    
    # 각 숫자마다 배수들에 약수 개수를 추가합니다.
    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            divisor_count[j] += 1
    
    # 3개가 넘는 약수를 가진 숫자들의 개수를 합칩니다.
    answer = sum(1 for i in range(n + 1) if divisor_count[i] >= 3)
    
    return answer

원래라면 소수가 아닌 값들을 삭제하는 용도지만, 반대로 개수를 미리 증가시키는 데 사용했습니다.

이 코드는 미리 배열에 저장해두기 때문에 좀 더 빠르게 구할 수 있습니다.

이론상 O(nlogn)의 시간 복잡도를 갖습니다.