[python] 소수 찾기

문제 출처

소수 찾기

 

풀이

import itertools

def solution(numbers):
    answer = 0
    numbers = sorted([int(i) for i in numbers], reverse=True)
    max_num = int(''.join([str(i) for i in numbers]))
    primes = [0, 0] + [1] * (max_num-1)
    for i in range(2, max(int(max_num**0.5), 2)):
        if primes[i]:
            for j in range(i+i, max_num+1, i):
                primes[j] = 0

    for i in range(1, len(str(max_num))+1):
        for comb in itertools.permutations(str(max_num), i):
            if comb[0] == '0':
                continue
            if primes[int(''.join(comb))]:
                primes[int(''.join(comb))] = 0
                answer += 1
    return answer