[오늘의 문제] 합성수 찾기

출처: https://school.programmers.co.kr/learn/courses/30/lessons/120846?language=python3

문제 설명
약수의 개수가 세 개 이상인 수를 합성수라고 합니다. 자연수 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 solution(n):
    answer = 0
    # 4, 6, 8, 9, 10, 12, 14, 15
    
    count = 0 # 약수 갯수
    numCount = 0 # 합성수 갯수 
    for i in range(1, n + 1): # 여기선 약수의 갯수를 센다.
        for j in range(1, i + 1): # 합성수 여부 계산    
          if i % j == 0:
            count += 1
            
        # 약수가 3개 이상이면 합성수이다.
        if count >= 3:
            numCount += 1
        
        count = 0
    
    return numCount

트러블 슈팅

일단 약수 갯수 세는 변수 합성수 갯수 세는 변수를 생각 한건 잘 했다.

하지만 맨처음에 약수 세는 로직을 반복문 두개 사이에 넣었다.

그리고 두번째 반복문 밖에 합성수 여부 파악하는 로직도 바깥에 넣어야 하는데 두번째 반복문 안에 넣었다.

거기다가. 합성수 여부까지 파악하면 count(약수 갯수) 초기화 하는것 까지 추가해야 했다.

다른 사람의 풀이

def solution(n):
    answer = 0
    for i in range(3,n+1) : # 3부터 n까지 반복
        temp = 1 # 약수의 개수를 저장할 변수 (i % 1 == 0 이므로 1로 시작)
        for j in range(1,i) : # 1부터 i-1까지 반복
            if i % j == 0 : # j가 i의 약수이면
                temp += 1 # 약수의 개수 증가
        
        if temp > 2 : # 약수의 개수가 2개 초과이면 (합성수이면)
            answer += 1 # 합성수 개수 증가
    return answer

첫번째거는 완전 유사하다.
1.반복 범위: 3부터 n까지의 자연수 i를 순회
2.약수 계산: 각 수 i에 대해 1부터 i-1까지의 수 j를 나누기
3.합성수 판별: 약수의 개수가 저장된 temp 값이 2를 초과하면 (temp > 2) i를 합성수로 간주한다.

def getcount(n): # n의 약수의 총 개수를 반환하는 함수
    count = 0
    for i in range(1, n + 1): # 1부터 n까지 반복
        if n % i == 0: # i가 n의 약수이면
            count += 1 # 약수의 개수 증가
    return count

def solution(n):
    answer = 0
    count = 0
    for i in range(1, n + 1): # 1부터 n까지 반복
        count = getcount(i) # i의 약수의 총 개수 계산
        if count > 2: # 약수의 개수가 2개 초과이면 (합성수이면)
            answer += 1 # 합성수 개수 증가
    
    return answer

약수를 세는 과정을 함수로 처리한 풀이다.

나머지는 다 비슷하다.

def solution(n):
    output = 0
    for i in range(4, n + 1): # 4부터 n까지의 자연수 i를 순회한다.
        for j in range(2, int(i ** 0.5) + 1): # j는 2부터 i의 제곱근까지 순회한다.
            if i % j == 0: # i가 j로 나누어 떨어진다면 (j는 i의 약수)
                output += 1 # 합성수 개수 증가
                break # 약수를 하나라도 찾으면 즉시 안쪽 반복문(j)을 종료한다.
    return output

1.반복 범위 (바깥): 4부터 n까지의 자연수 i를 순회
2.효율적인 약수 검사 (안쪽): 각 수 i에 대해 2부터 sqrt{i}까지의 수 j를 순회하며 약수를 찾는다.
3.합성수 판별 및 종료: 약수 j를 단 하나라도 찾으면, i는 합성수이므로 output을 1 증가시키고, break를 사용하여 안쪽 for j 반복문을 즉시 종료