[programmers/python] 소수찾기 - 완전탐색, 에라토스테네스의 체

프로그래머스 ‘소수 찾기’ 문제는 주어진 숫자 문자열로 만들 수 있는 모든 수를 조합해, 그중 소수의 개수를 구하는 완전탐색 문제다.
처음에는 하나하나 소수 판별을 직접 하는 방식으로 해결할 수 있지만, 더 효율적인 방법은 ‘에라토스테네스의 체’를 활용해 소수 정보를 미리 계산해두는 것이다.

 

• url : https://school.programmers.co.kr/learn/courses/30/lessons/42839?language=python3

---

1. 문제 핵심

• 문자열 numbers로 만들 수 있는 모든 숫자 조합을 생성
• 중복 없이 set에 담고, 그중 소수만 카운팅
• isPrime()을 수십 번 호출하지 않고, 소수 배열을 미리 캐싱하는 방식으로 개선

---

2. 에라토스테네스의 체

def make_sieve(limit):
    is_prime = [False, False] + [True] * (limit - 1)
    for i in range(2, int(limit ** 0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, limit + 1, i):
                is_prime[j] = False
    return is_prime

• limit까지의 소수 여부를 미리 계산
• 이후엔 is_prime[n]만으로 소수인지 즉시 확인 가능 (O(1))

---

3. 최종 코드

from itertools import permutations

def make_sieve(limit):
    is_prime = [False, False] + [True] * (limit - 1)
    for i in range(2, int(limit ** 0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, limit + 1, i):
                is_prime[j] = False
    return is_prime

def solution(numbers):
    number_set = set()
    for i in range(1, len(numbers) + 1):
        for p in permutations(numbers, i):
            number_set.add(int(''.join(p)))
    
    sieve = make_sieve(max(number_set))
    return sum(1 for n in number_set if sieve[n])