[프로그래머스/파이썬] 소수 찾기

 

나의 풀이

from itertools import permutations
from math import sqrt


def is_prime(num):
    if num < 2 :
        return False
    for n in range(2, int(sqrt(num) + 1)):
        if num % n == 0:
            return False
    return True


def solution(numbers):
    temp = []

    for i in range(1, len(numbers) + 1):
        temp.extend(list([int(''.join(num)) for num in permutations(numbers, i)]))

    return sum([is_prime(x) for x in list(set(temp))])

 

 

set를 이용한 풀이

from itertools import permutations
def solution(n):
    a = set()
    for i in range(len(n)):
        a |= set(map(int, map("".join, permutations(list(n), i + 1))))
    a -= set(range(0, 2))
    for i in range(2, int(max(a) ** 0.5) + 1):
        a -= set(range(i * 2, max(a) + 1, i))
    return len(a)

 

 

재귀 함수를 이용한 풀이

primeSet = set()


def isPrime(number):
    if number in (0, 1):
        return False
    for i in range(2, number):
        if number % i == 0:
            return False

    return True


def makeCombinations(str1, str2):
    if str1 != "":
        if isPrime(int(str1)):
            primeSet.add(int(str1))

    for i in range(len(str2)):
        makeCombinations(str1 + str2[i], str2[:i] + str2[i + 1:])


def solution(numbers):
    makeCombinations("", numbers)

    answer = len(primeSet)

    return answer

 

 

 

defaultdict를 이용한 풀이

from itertools import permutations
from collections import defaultdict

def is_prime(n):
    return all([(n%j) for j in range(2, int(n**0.5)+1)]) and n>1

def solution(numbers):
    count = 0
    history = []
    for n in range(len(numbers)):
        for digit_arr in permutations(numbers, n+1):
            number = 0

            for i, digit in enumerate(digit_arr):
                b = len(digit_arr) - i - 1
                number += int(digit) * (1*(10**b))

            if number not in history and is_prime(number):
                history.append(number)
                count+=1

    return count