[프로그래머스] 소수 찾기 - Python

Algorithm Problem with Python — 16day

문제 설명 📖

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

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

제한사항

• n은 2이상 1000000이하의 자연수입니다.

입출력 예

문제 이해 🔑

1부터 주어진 인풋 사이에 소수가 있는지 판별하고 총 소수의 개수를 구하는 문제입니다.
소수를 구하는 알고리즘을 작성해야 하는데 대표적인 알고리즘으로 에라토스체네의 체가 있습니다.
소수를 구하는 알고리즘을 이해하고 있는지, 사용할 수 있는지 확인하는 문제입니다.

수도 코드 ✍️

에라토스체네스의 체의 원리를 이용합니다.

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.

2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)

3. 자기 자신을 제외한 2의 배수를 모두 지운다.

4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)

5. 자기 자신을 제외한 3의 배수를 모두 지운다.

6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)

7. 자기 자신을 제외한 5의 배수를 모두 지운다.

8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)

9. 자기 자신을 제외한 7의 배수를 모두 지운다.

10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

11. 그림의 경우, 11^2>120 이므로 11보다 작은 수의 배수들만 지워도 충분하다.
    즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

코드 작성 ⌨️

def solution(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True]*(n+1)
    
    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(n ** 0.5)
    for i in range(2, m+1):
        if sieve[i] == True: # i가 소수인 경우
            for j in range(i*i, n+1, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

    x = [i for i in range(2, n+1) if sieve[i] == True]
    answer = len(x)
    return answer

정리 😄

소수를 찾는 문제이나 어떻게 코드로 작성할 수 있을지 고민을 하였습니다.
소수를 구하는 알고리즘을 찾아보았고 위키백과를 통해 에라토스체네스의 체를 공부하였습니다.
프로그래머스 1단계에서 유용하게 사용되는 알고리즘들을 공부해 두어야 2단계에서 응용된 문제를 해결할 수 있겠다고 느꼈습니다.