[python] 소수 찾기(연습문제)

문제는 간단하다 1부터 입력받은 숫자 n까지 중 소수가 몇 개 있는지 반환하면 된다.

n이 10이라면 1부터 10에는 2, 3, 5, 7 총 4개의 소수가 존재하므로 4를 반환하고 5라면 2, 3, 5 총 3개의 소수가 존재하므로 3을 반환한다.

 

설계 및 구현

주어진 함수는 n을 입력받아 개수를 반환하면 되는 함수이다. 소수의 개수를 구하는 알고리즘은 에라토스테네스의 체를 사용하면 된다. 내용은 2부터 소수를 구하고자 하는 구간의 모든 수를 나열하고 2는 소수이므로 2를 제외한 2의 배수들을 모두 지운다. 그다음 남은 수중 3은 소수이므로 제외하고 3의 배수를 모두 지운다. 이처럼 소수들의 배수들을 모두 지우는 과정을 반복하면 결국 소수만 남게 된다. 정리하면

① n까지의 모든 숫자 나열

② 2의 배수, 3의 배수... 남은 소수들의 배수 모두 지우기

 

①을 수행하기 위해 소수판별을 위한 숫자를 리스트에 넣는 것이 아닌 인덱스로 사용한다. 리스트에 n+1의 개수만큼 True로 만든다. 1부터가 아닌 2부터로 판단할 것이므로 n+1개만큼 만들어낸다.

②의 수행 과정으로 반복문을 n의 제곱근만큼만 수행한다. 이유는 배수를 지워내는데 최대 크기인 n의 약수중 가장 큰 수는 n의 제곱근이기 때문에 n까지 전부 확인할 필요가 없기 때문이다. 반복을 수행하며 배수들의 인덱스에는 소수가 아니기 때문에 True대신 False를 삽입한다. 마지막으로 해당 리스트를 가지고 2~n까지의 모든 숫자 중 True인 곳의 숫자는 추가하고 False인 곳의 숫자는 추가하지 않아 소수만 가지고 있는 리스트의 길이를 반환한다.

 

위와 같은 방법을 수행하면 불필요한 연산이나 비교가 들어가지 않아 시간복잡도가 반복문의 횟수만큼만 걸리기 때문에 효율성 테스트를 통과할 수 있다.