[Python] 소수 찾기 - 에라토스테네스의체 이용 (프로그래머스 Lv.1)
소수 찾기
- Link: 프로그래머스에서 문제 확인하기
문제:
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.)
삽질의 연속
이 문제를 푸는데 사실 적지 않은 시간이 걸렸다. 지금까지 풀었던 문제들은 기초 단계였기에 효율성 테스트가 빡빡하지 않았다. (아님 내가 잘 짠 걸지도…? 모르지만) 아래의 코드는 제대로 작동은 되지만, 시간 초과로 효율성 통과를 하지 못했다. n만큼 반복되는 for문 안에 또 for문이 있으니 효율성이 구릴 수 밖에 없지 않나.. 뭐.. 어쨌든 돌아가긴 한다.
제출했던 코드
def solution(n):
answer = []
for i in range(1, n+1):
sum = 0
for j in range(1, n+1):
if i % j == 0:
sum += 1
if sum == 2:
answer.append(sum)
return len(answer)
1~n까지 반복되는 반복문 두 개를 서로 나누었을 때 나머지가 0이 될 때, 즉 나누는 수가 그 수의 약수일 때, sum을 1씩 늘려주었다. 소수는 1과 그 자신으로만 나누어지는 수이기 때문에 약수가 2개일 때의 갯수를 리턴해주는 함수를 구현하였다.
에라토스테네스의 체를 이용한 풀이
머릿속을 굴려보았지만, 내가 알고 있는 방법들로는 이 문제를 통과할 수가 없었고, 나는 검색 후 에라토스테네스의 체라는 방법을 이용하면 효율성을 엄청 높일 수 있다는 것을 알게 되었다.
- 에라토스테네스의 체?: 2보다 크거나 같고 n보다 작은 소수의 배수를 지우면서 소수를 찾는 방법
아래의 위키백과에서 gif 설명과 c++, java, python 등의 언어로 간단한 코드 예제도 올라와있다.
에라토스테네스의 체: 위키백과 참조
즉, 1~n 까지의 수 중에서 소수를 뽑아낼 수 있다. => 이 문제와 찰떡 궁합인 셈!
에라토스테네스의 체를 이용한 풀이
def solution(n):
num=set(range(2,n+1))
for i in range(2,int((n+1)**0.5)+1):
num -= set(range(2*i,n+1,i))
return len(num)
결국 모아둔 포인트(프로그래머스에서는 알맞은 코드를 제출하면 점수를 얻을 수 있다.)를 사용하여 다른 사람의 코드를 참고하였다. 문제 하나 풀면 1~10점 정도 주는데, 한 번 보려면 30점 정도 까이는 것 같다.
차집합을 이용한 풀이다. 리스트와 달리 집합 자료형은 순서가 뒤죽박죽인 대신 교집합, 차집합, 합집합 등을 연산에 사용할 수 있다고 한다.
set(): 집합 자료형으로 만들어주는 함수 => “차집합(-), 교집합(&), 합집합(|)”
num에 set함수를 이용하여 2부터 n까지 수를 만든 후, i 이후 i의 배수들의 집합을 빼주어서 답을 구했다.
소수 문제는 알고리즘 문제에 자주 나오는 편이라고 하니깐, 꼭 기억해두었다가 다음에 소수 찾는 문제가 나오면 사용해봐야겠다.