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

- 문제 설명

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

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

- 제한 조건

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

- 입출력 예

n	result
10	4
5	3

 

- 입출력 예 설명

입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

---

 

소수 찾기 문제는 알고리즘 문제에서도 약수 문제와 아주 단골 문제이죠. 소수 찾기에 대한 알고리즘을 공부해보신 분이라면 '에라토스테네스의 체' 라는걸 들어보셨을 겁니다.

위키에 나와있는 이 글을 참고해주신다면 아래의 코드 및 설명의 이해가 쉬울거라 생각됩니다..!

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

일단 소수(Prime Number)라는 것은 1과 자신 이외에 약수가 없는 수를 뜻하는데 정말 간단하게 완전 탐색으로 코드를 작성한다면 number보다 작거나 같은 수들을 하나씩 차례로 나누어져서 소수를 판별하는 방법도 있겠지만 이 방법은 number값이 크게 될 경우 연산량이 기하급수적으로 늘어나기 때문에 효율적인 코드가 될 수 없습니다.

따라서, 우리는 에라토스테네스의 체(이름 어렵네요..) 를 사용해서 소수를 판별을 위한 연산 횟수를 줄일 것입니다. 에라토스테네스의 체에 대한 자세한 설명은 각설하고.. 방법론에 대한 내용을 얘기하자면

일단 짝수는 소수가 될 수 없으므로 n 미만의 자연수들 중 홀수들 만을 뽑아냅니다.

a=[ i for i in range(3,n+1,2)]

a 라는 배열에는 3부터 시작하는 n 미만의 자연수 배열이 들어갑니다. 이제 이 배열에서 배수들을 에라토스테네스의 체를 이용해서 모두 걸러낼 것입니다.

ex) a의 첫 번째 인덱스의 값인 3의 배수들 제거 [3,5,7,9,11,13,15,17...] => [3,5,7,11,13,17...] 

    5의 배수 제거, 7의 배수 제거... 11의 배수 제거.. 13의 배수 제거...... 

를 n미만의 자연수까지 진행하게 된다면 소수들만 남게됩니다. 이 내용을 코드로 간략화 시키면,

def solution(n):
    a=set([ i for i in range(3,n+1,2)])
    for i in range(3,n+1,2):
        if i in a: 
            a-=set([i for i in range(i*2,n+1,i)])
    return len(a)+1

a-=set([i for i in range(i*2,n+1,i)] 라는 것은 i가 3이라면 3을 제외한 x2 즉, 자신을 제외한 배수 값들을 차례대로 제거해 나가서 a를 에라토스테네스의 체로 걸러낸 것을 의미합니다. 

소수를 판별하기 위한 에라토스테네스의 체를 파이썬으로 간결하게 구현해 본 예제였습니다.