📜문제 설명
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)
📍제한 사항
- n은 2이상 1000000이하의 자연수입니다.
📍입출력 예시
| n | return |
|---|---|
| 10 | 4 |
| 5 | 3 |
📄문제 해결
📝내가 푼 코드
이 문제는 소수를 찾는다는 단순한 문제임에도 시간, 메모리 측면에서 효율적이어야 했기에 레벨 1 문제임에도 정답률은 낮은 축에 속했다.
def solution(n):
answer = n - 1
for i in range(4, n + 1):
for j in range(2, i // 2 + 1):
# 나눠지면 소수가 아니다
if i % j == 0:
answer -= 1
break
return answer소수를 찾는다는 것에 집중해 위와 같이 직관적인 코드를 작성했으나, 시간 초과라는 문제에 직면했다.
나눠지면 소수가 아니라는 점을 활용한 코드는 결국 n보다 작은 숫자로 일일이 나눠보기 때문에 숫자 범위가 커지면 효율적이지 못하다는 문제를 갖는다.
이때 이 문제를 해결하기 위해 아레토스테네스의 체라는 개념을 새롭게 공부하여 새로운 코드를 작성했다. (자세한 내용은 나의 벨로그에서 확인할 수 있다.)
def solution(n):
a = [False, False] + [True] * (n - 1)
for i in range(2, n + 1):
if a[i]: # i는 소수인가?
for j in range(2 * i, n + 1, i):
a[j] = False
return sum(a)결과는 성공적이었다! 빠른 속도로 문제를 해결할 수 있었다.
True, False의 값을 갖는 리스트를 활용해 위와 같이 소수의 개수를 구하는 코드는 굉장히 효율적이었다. 실제 값을 저장하지 않기 때문에 더욱 그런 것으로 보인다.
📑다른 사람들의 풀이
def solution(n):
num=set(range(2,n+1))
for i in range(2,n+1):
if i in num:
num -= set(range(2*i,n+1,i))
return len(num)에라토스테네스의 체를 범위의 숫자가 담긴 set로 구현했다. 그리고 배수를 삭제할 때, 또다른 for문을 통해 각각 삭제하는 것이 아니라 range를 통해 i의 배수가 담긴 집합을 만들어 차집합을 구했다.
코멘트를 보니 간단하고 집합을 통해 에라토스테네스의 체를 구현한 점에서 좋아 보이는 코드는 맞으나, 차집합 연산 시 매번 num 전체를 읽기 때문에 내가 짠 것처럼 리스트를 이용하는 것이 속도와 메모리 효율 모두 좋다는 코멘트를 보았다.
이를 확인하기 위해 각 코드를 테스트해 보니 리스트를 활용한 것이 훨씬 효율적이라는 것을 확인할 수 있었다.
🤔느낀점
시간복잡도, 메모리 측면에서 아쉬운 코드지만, 에라토스테네스의 체를 이와같이 활용할 수 있다는 점은 충분히 공부가 되었다.
