백준 3671 <산업 스파이의 편지> Python

https://www.acmicpc.net/problem/3671

---

소수 판정 + 순열 문제입니다.

우선 숫자가 7개까지 입력되니 10e8 이하의 소수를 모두 구해주면 됩니다.

한계가 큰 만큼 에라토스테네스의 체 알고리즘을 사용하면 편하게 구할 수 있습니다.

 

그리고 그 중 조합할 수 있는 수를 구하는 경우는 permutation 을 통해 모든 조합을 구한 뒤 set 을 사용해 중복을 제거한 뒤 소수인지 판정해주면 되겠습니다.

---

import sys
from itertools import permutations

input = sys.stdin.readline

    
def solution(c, nums):
    # 7자리 이하 소수 모두 구하기
    limit = 10000000
    # 소수 판정 리스트
    is_prime = [1 for _ in range(limit+1)]
    is_prime[0] = 0
    is_prime[1] = 0
    # 순회
    for num in range(int(pow(len(is_prime), 1/2))+1):
        # 해당 수가 소수면
        if is_prime[num]:
            # 배수 모두 소수가 아님
            for n in range(2*num, len(is_prime), num):
                is_prime[n] = 0

    # 수 조합
    for n in nums:
        # 조합된 수 셋
        c_nums = set()
        # 조합할 수 개수
        for i in range(1, len(n)+1):
            for c_n in permutations(n, i):
                # 조합된 수
                c_nums.add(int(''.join(c_n)))

        print(sum([1 for num in c_nums if is_prime[num]]))


# 입력
c = int(input().strip())
nums = [input().strip() for _ in range(c)]

solution(c, nums)