출처 : https://school.programmers.co.kr/learn/courses/30/lessons/42839
- 숫자로 이루어진 문자열 numbers의 인자들로 만들 수 있는 숫자 중 소수의 개수를 구하라
- 주어진 문자열로 만들 수 있는 숫자 조합을 모두 구해 set에 담는다.
- set에 담긴 최댓값을 기준으로 에라토스테네스의 체를 구현해 set안의 수가 소수인지 판별한다.
# 소수 판별 함수
def che(combi):
# 문자열로 변환한 숫자 중 가장 큰 수를 기준으로
m = max(combi)
v = [0] * (m + 1)
# 에라토스테네스의 체 구현
for i in range(2, int(m ** 0.5) + 1):
# 이 때, v[i]가 0이라면 소수다!
if not v[i]:
for j in range(i * 2, m + 1, i):
v[j] = 1
value = 0
for i in combi:
# i가 0이거나 1이면 소수가 아님
if i < 2:
continue
# v[i]가 0면 소수
if not v[i]:
value += 1
return value
def dfs(num, s):
global combi
# 만들어진 수는 set에 담는다
combi.add(int(num))
# s가 빈 문자열이면 멈춤
if not s:
return
for i in range(len(s)):
dfs(num + s[i], s[:i] + s[i + 1:])
def solution(numbers):
global combi
combi = set()
# 일단 숫자를 만들고
for i in range(len(numbers)):
if numbers[i] != "0":
dfs(numbers[i], numbers[:i] + numbers[i + 1:])
# 소수가 몇 개인지 return
return che(combi)