Algorithm Problem with Python — 16day
문제 설명 📖
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)
제한사항
- n은 2이상 1000000이하의 자연수입니다.
입출력 예
문제 이해 🔑
1부터 주어진 인풋 사이에 소수가 있는지 판별하고 총 소수의 개수를 구하는 문제입니다.
소수를 구하는 알고리즘을 작성해야 하는데 대표적인 알고리즘으로 에라토스체네의 체가 있습니다.
소수를 구하는 알고리즘을 이해하고 있는지, 사용할 수 있는지 확인하는 문제입니다.
수도 코드 ✍️
에라토스체네스의 체의 원리를 이용합니다.
-
2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
-
2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
-
자기 자신을 제외한 2의 배수를 모두 지운다.
-
남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
-
자기 자신을 제외한 3의 배수를 모두 지운다.
-
남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
-
자기 자신을 제외한 5의 배수를 모두 지운다.
-
남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
-
자기 자신을 제외한 7의 배수를 모두 지운다.
-
위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.
-
그림의 경우, 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단계에서 응용된 문제를 해결할 수 있겠다고 느꼈습니다.
