백준 3671 산업스파이의 편지 (Python, Pypy)

#3671 산업스파이의 편지
import sys
import math
from itertools import permutations
from itertools import combinations

N = int(input())
A = []

def f(n):
    if n == 0:
        return False
    elif n == 1:
        return False
    else:
        for i in range (2,int(math.sqrt(n))+1):
            if n % i == 0:
                return False
            else:
                continue
        return True

for i in range (0,N):
    a = input()
    A.append(a)

for i in range (0,N):
    prime = []
    for j in range (1,len(A[i])+1):
        num_list = list(A[i])
        for num in permutations(num_list,j):
            s = "".join(t for t in num)
            s = int(s)
            if f(s) == True:
                prime.append(s)
            else:
                continue
    prime = list(set(prime))
    m = len(prime)
    print(m)

Permutations을 잘 쓰면 되는 상황이고,
Permutations을 통해 찾아낸 숫자에 대해 소수판정을 해주는 방침으로 풀 수 있습니다.

파이썬 기준 2506ms가 나온 것으로 보아 정말 아슬아슬하게 푼듯한 느낌이네요.