[프로그래머스][파이썬] 합성수 찾기 - 수학 (Level 0)

◽ 문제 출처

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

◽ 문제

◽ 입력 & 출력

◽ 내 풀이

def solution(n):
    answer = 0

    for i in range(1, n + 1):
        divisor = []
        
        for j in range(1, i + 1):
            if i % j == 0:
                divisor.append(i)
                
        if len(divisor) >= 3:
            answer += 1
            
    return answer

• 1부터 n까지 반복하면서 약수들을 담아둘 지역 변수 divisor을 먼저 초기화한다.
• 1부터 자기자신까지 약수 대상인지 체크하고, 약수라면 divisor 리스트에 추가한다.
• divisor 리스트의 길이가 3개 이상이면, 합성수이므로 개수를 추가한다.
  
  

◽ 다른 사람 풀이

def solution(n):
    output = 0
    
    for i in range(4, n + 1):
        for j in range(2, int(i ** 0.5) + 1):
            if i % j == 0:
                output += 1
                break
                
    return output

• 소수 판별하는 문제에서 자주 등장하는 에라토스테네스의 체 알고리즘 풀이인듯 하다.
• 하지만, 합성수는 소수가 아닌 자연수로 설명할 수 있다.
• 1 ~ 3 은 합성수가 될 수 없으니 4 부터 순회한다.
• i 가 j 의 배수라면 i 는 합성수이므로, 개수 추가. (배수가 아니라면 소수)
  
  

◽ 더 나아가기

• 에라토스테네스의 체 알고리즘의 시간 복잡도는 O(nloglogn) 정도로 사실상 선형시간에 가깝다고 한다.
• 에라토스테네스의 체 예시) 16 의 약수는 1, 2, 4, 8, 16 이지만, sqrt(16) = 4 까지만 보면 2 와 4 를 찾을 수 있고, 약수는 a * b 쌍으로 존재하므로, 작은 쪽만 확인하면 큰 약수도 자동으로 판별된다.
  
  
  
  

피드백은 언제나 환영입니다 :)