Python으로 n 이하의 모든 소수 목록 생성하기

Python에서 n 이하의 소수 목록 생성 방법

숫자 n이 하나 주어졌다고 가정해 봅시다. 이때 n보다 작거나 같은 모든 소수(prime number)를 오름차순으로 정렬된 리스트 형태로 생성해야 합니다. 여기서 한 가지 주의할 점은 1은 소수가 아니라는 사실입니다.

예를 들어 입력값이 12라면, 출력 결과는 다음과 같습니다.

[2, 3, 5, 7, 11]

문제 해결 접근 방식

이 문제는 고전적인 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘을 활용하면 효율적으로 해결할 수 있습니다. 구체적인 단계는 다음과 같습니다.

• sieve := 크기가 n+1인 리스트를 생성하고, 모든 요소를 True로 초기화합니다.
• primes := 소수를 저장할 빈 리스트를 하나 준비합니다.
• i를 2부터 n까지 반복합니다.
  • 만약 sieve[i]가 True라면:
    • primes 리스트의 끝에 i를 추가합니다.
    • j를 i부터 n까지 i씩 증가시키며 반복하면서, 각 위치의 sieve[j] 값을 False로 변경합니다. (i의 배수는 모두 소수가 아니므로 제외)
• 최종적으로 primes 리스트를 반환합니다.

아래 예제 코드를 통해 더 자세히 이해해 보겠습니다.

예제 코드

class Solution:
   def solve(self, n):
      sieve = [True] * (n + 1)
      primes = []
      for i in range(2, n + 1):
         if sieve[i]:
            primes.append(i)
            for j in range(i, n + 1, i):
               sieve[j] = False
      return primes
ob = Solution()
print(ob.solve(12))

입력

12

출력

[2, 3, 5, 7, 11]

동작 원리와 성능

위 코드는 먼저 인덱스 0부터 n까지의 불린(Boolean) 배열을 만들어 각 수가 소수 후보인지 표시합니다. 그런 다음 2부터 시작하여 아직 True로 남아 있는 수를 발견하면 그 수를 소수 목록에 추가하고, 해당 수의 모든 배수를 False로 바꿔 이후 탐색 대상에서 제외합니다. 이 과정을 반복하면 자연스럽게 n 이하의 모든 소수가 오름차순으로 수집됩니다.

이 알고리즘의 시간 복잡도는 O(n log log n)으로, 각 수마다 일일이 약수 여부를 검사하는 단순 반복 방식(O(n√n))보다 훨씬 빠릅니다. 따라서 n이 수백만 단위로 커져도 안정적으로 동작한다는 장점이 있습니다.