파이썬으로 소수 개수 세기: 에라토스테네스의 체 활용법

문제 정의

하한값 n이 주어졌을 때, 2부터 n까지 범위에 존재하는 소수(prime number)의 개수를 구하는 문제입니다. 예를 들어 n = 10이라면, 10보다 작은 소수는 2, 3, 5, 7로 총 4개이므로 결과는 4가 됩니다.

해결 접근 방식: 에라토스테네스의 체

이 문제는 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 소수를 하나 발견할 때마다 그 소수의 배수들을 모두 '합성수'로 표시하여, 이후 탐색에서 제외하는 것입니다.

구체적인 진행 과정은 다음과 같습니다.

• 소수 개수를 저장할 변수 count = 0으로 초기화합니다.
• 크기가 n + 1인 배열 prime을 만들고, 모든 값을 False(소수 후보)로 채웁니다.
• i = 2부터 n-1까지 반복합니다.
  • 만약 prime[i]가 False라면 i는 소수이므로:
    • count를 1 증가시킵니다.
    • j = 2로 설정한 뒤, j * i < n을 만족하는 동안 prime[i * j]를 True(합성수)로 표시하고 j를 1씩 증가시킵니다.
• 반복이 끝나면 count를 반환합니다.

파이썬 구현 예제

아래 코드를 통해 실제 구현 방법을 확인할 수 있습니다.

class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        count = 0
        primes = [False for i in range(n+1)]
        for i in range(2, n):
            if primes[i] == False:
                count += 1
                j = 2
                while j * i < n:
                    primes[j * i] = True
                    j += 1
        return count

ob1 = Solution()
print(ob1.countPrimes(50))
print(ob1.countPrimes(10))

입력

n = 50
n = 10

출력

15
4

동작 원리와 시간 복잡도

n = 10인 경우를 살펴보면, 2가 소수임을 확인한 순간 4, 6, 8이 합성수로 표시되고, 3에서는 6, 9가 표시됩니다. 결국 5와 7은 이미 표시되지 않은 상태로 남아 있어 소수로 카운트되며, 최종 결과는 4가 됩니다.

이 알고리즘의 시간 복잡도는 O(n log log n)으로, 각 수마다 일일이 나눗셈으로 소수 여부를 판별하는 단순 방식(O(n√n))보다 훨씬 빠릅니다. 따라서 n이 수백만에 달하는 큰 값이 주어져도 충분히 빠른 속도로 소수의 개수를 계산할 수 있습니다.