에라토스테네스의 체

수학에서 에라토스테네스의 체는 소수를 찾는 방법입니다. 고대 그리스 수학자 에라토스테네스가 발견하였습니다.

 

방법은 다음과 같습니다.

 

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열합니다.

2. 2는 소수이므로 소수 리스트에 적어두고,

3. 자기 자신을 제외한 2의 배수를 모두 지웁니다.

4. 남아 있는 수 가운데 3은 소수 이므로 소수 리스트에 적어두고,

5. 자기 자신을 제외한 3의 배수를 모두 지웁니다.

6. 위의 과정을 반복하면 구하는 구간의 모든 소수를 찾을 수 있습니다.

 

다음은 파이썬을 이용한 예시이며, 소수인지를 체크할 수 있는 배열 정보와 소수 리스트를 리턴해 줍니다.

 

def findPrimes(n):
        tPrimes = [2]
        tArr = [True] * (n+1)
        tArr[0], tArr[1] = [False] * 2

        for i in xrange(4, n+1, 2):
                tArr[i] = False

#        for i in xrange(3, n+1, 2):
#                j = 3
#                while True:
#                        tmp = i * j
#                        if (tmp > n):
#                                break
#                        tArr[tmp] = False
#                        j += 2

        for i in xrange(3, int(n**0.5)+1, 2):
            if (tArr[i]):
                for j in xrange(i**2, n+1, 2*i):
                    tArr[j] = False

        for i in xrange(3, n+1, 2):
                if (tArr[i]):
                        tPrimes.append(i)

        return tArr, tPrimes