programmers - 소수찾기[level1] - python (에라토스테네스의 체)

소수찾기 문제는 알고리즘 문제 중에 기본 중에 기본이다.

 

이번에 정말 오랜만에 Programmers에 가서 소수찾기라는 문제를 풀면서 좀 헤멘부분이 있어서 공부할겸 블로그에 다시 정리 해보도록 한다.

 

에라토스테네스의 체를 설명하자면, 

 

(출처 : 위키백과)

 

소수를 찾는 방법 중 하나이다.

 

간단하게 설명하자면, 소수들의 배수를 지워나가면서 검증 방식을 최소화 시킨 방법이다.

-> 소수들의 배수들은 소수가 될수없으니까

 

좀 자세히 설명을 덧붙이자면, 2부터 검증을 할시(0과 1은 소수가 아니니까.)

 

2는 소수이니 2는 따로 빼놓고 2를 제외한 2의 배수들(2, 4, 6, 8, ...)을 소수여부를 검증(제외)한다.

3은 소수이니 3은 따로 빼놓고 3을 제외한 3의 배수들(3, 9, 15, 21, ...)을 소수여부를 검증(제외)한다.

-> 이 부분에서 6과 12가 제외 된 이유는 앞에서 2의 배수들을 검증 할때 6과 12는 이미 2의 배수기 때문에 제외 됐기 때문

4는 이미 앞에서 2의 배수로써 앞에서 제외되었기 때문에 패스.

5은 소수이니 5는 따로 빼놓고 5를 제외한 5의 배수들(5, 25, 35, 55, ...)을 소수여부를 검증(제외)한다.

-> 이 부분에서 마찬가지로 10, 15, 20, 30 등은 앞의 2, 3의 배수로써 제외됐다.

 

이런 식으로 소수를 검증하는 속도를 올릴 수 있는 알고리즘이 "에라토스테네스의 체"이다.

 

 

그리고 100안의 소수의 개수를 찾는다고 꼭 2에서 100까지 검증 할 필요는 없고 100 ** 1/2만큼 (즉 루트100 = 10 만큼) 검증하면된다.

 

n까지의 소수를 검증할 시 어떠한 수 m이 a와 b를 약수로 가질때 a와 b 둘중 하나는 무조건 루트n이하이다. 그러므로 앞에서 n이하의 소수 들은 루트n까지 검증을 마치더라도 앞에서 검증이 이미 다 되었다는 소리다.

 

예를 들어보자면

 

49 이하의 소수를 구할 땐 7까지 소수 검증(에라토스테네스의 체)을 하면 된다는 소리다.

 

48을 소수검증을 한다고 하면 2^4 * 3이 된다. (2와 3은 7이하의 수이고,  2의 배수를 검증할 때 이미 제외되었다)

47은 제외되지 않고 남은 소수이다.

...

 

이런식으로 계산이 된다.

 

10 이후의 소수

11, 22, 33, 44이고 11을 제외한 22, 33, 44는 앞에서 다 제외가 되었다.

17은 17, 34, 51, 68 17을 제외한 34, 51, 68 도 역시 앞에서 다 제외가 되었다.

 

(11과 17은 제외되고 남은 소수일 것이다.)

 

 

결국

루트n까지의 소수 + (루트 n까지의 소수로) 소수가 아님을 검증한 수를 제외 한 수) = n까지의 소수가 되는 것이다.

 

 

 

 

이제는 programmers의 문제를 보겠다.

 

 

 

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

def solution(n): #n의 제곱근 이하의 소수만 판별 해 내면 됨.
    a = [False, False] + [True] * (n-1)
    for i in range(2, int(n ** 0.5)+1):
        if a[i]:
            for j in range(i*2, n+1, i):
                a[j] = False
                
    return a.count(True)

 

boolean배열로 계산이 편해지도록 마지막 배열이 a[n]이 되도록 맞춰서 배열을 선언한다.

(선언시 0과 1은 소수가 아님을 나타내는 False로 선언하고 나머지는 모두 소수임을 가정하여 True로 선언한다.)

 

그리고 2부터 루트n까지 도는 반복문을 만든다.

 

만약 a[i]가 소수라면 배열을 돌면서 i를 제외한(i*2) i의 배수 배열들을 다 False시킨다. (소수가 아니라고 표시한다.)

-> 이 부분에서 2와 3은 처음부터 소수라고 선언했기 때문에 무조건 조건문에 포함된다.

하지만 4부터는 2에서 다시 반복문을 돌면서 False시켰기에 4의 배수들을 제외하는 작업을 하지 않는다.

 

 

 

그리고 소수의 개수를 리턴한다.