[Python] programmers, 프로그래머스 소수 찾기 Lv.1 (feat.에라토스테네스의 체)

반짝반짝 알고리즘, 인프준

 

 

소수 찾기

문제 링크

프로그래머스

 

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. ( 1은 소수가 아닙니다. )

 

제한 조건

n은 2 이상 1,000,000 이하의 자연수입니다.

 

 

입출력 예

n	result
10	4
5	3

 

입출력 예 설명

입출력 예#1

1부터 10 사이의 소수는 [ 2, 3, 5, 7 ] 4개가 존재하므로 4를 반환한다.

 

입출력 예#2

1부터 5 사이의 소수는 [ 2, 3, 5 ] 3개가 존재하므로 3을 반환한다.

 

 

 

해결 과정

문제를 읽고 첫 접근은 제한 조건 범위 내에 모든 수를 확인하여 소수인지 확인하는 방법으로 시작했습니다. 이중 for loop를 돌며 하나하나 확인을 거치는 투박한 코드를 아래와 같이 작성했습니다.

def solution(n):
    answer = 0   
    for i in range(2, n+1):     # 2부터 n까지
        for j in range(2, i):   # 소수 찾기
            if i % j == 0:      # 나머지가 0이라면 '합성수'
                break
        else:                   # for문이 끝까지 돌았다면 '소수'
            answer += 1
    return answer

 

위 코드는 테스트 케이스에서 실행 성공했지만 n의 값이 커질수록 실행시간이 커지기 때문에 이 코드는 일부 케이스에서 시간 초과가 발생하고 효율성 테스트에서 실패합니다.

 

 

찾아보니 n의 제곱수 판별은 n-1까지 확인하지 않고 n의 제곱근까지만 나눠보면 판별이 가능하다는 것과 2의 배수와 3의 배수만 제외시켜도 코드가 동작할 수 있다고 알게 되었지만 에라토스테네스의 체를 활용하면 터무니없이 간단하게 풀려 공부 겸 기록해 봅니다.

 

 

또 다른 풀이

 

에라토스테네스의 체

1. 2부터 n까지 숫자를 나열
2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾음
3. 남은 수 중에서 i의 배수를 제거
4. 더 이상 제거할 수 없을 때까지 반복

 

def solution(n):
    arr = set(range(2, n+1))
    
    for i in range(2, n+1):
        if i in arr: # 남은 수 중 가장 작은 i
            arr -= set(range(2*i, n+1, i))
    return len(arr)

 

 

정말 간단하고 깔끔하게 해결됩니다. 알고리즘은 이해가 안 될 때는 정말 지루하고 재미없지만 이해하고 나면 세상 재밌는 묘한 매력을 가지고 있었음을 다시 한번 느끼게 해 준 문제였습니다. 또한 실무에서도 기술적인 최적화 작업을 진행하기 전에 문제를 바라보는 시각과 이해하는 능력의 중요함을 강조하게 됩니다.

 

 

 

 

 

---

 

 

 

 

출처: 프로그래머스 코딩 테스트 연습,  https://school.programmers.co.kr/learn/challenges