[python] 프로그래머스 - 소수 찾기

 문제링크  : https://programmers.co.kr/learn/courses/30/lessons/42839

코딩테스트 연습 - 소수 찾기

 

 

 문제 설명 

 

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하는 solution 함수

 

 알고리즘 

 

1. 주어진 숫자를 분리하여 만들수 있는 숫자를 모두 구한다 (조합 이용)

2. 소수를 구하는 함수를 작성하여 모둔 경우의 숫자에 대해 소수를 판별한다

3. 소수 갯수 return

 

 코드 

# 소수 찾기 
 
from itertools import permutations
import math
def prime(num):
    if num in [0,1]: return False
    pos = True
    for i in range(2,int(math.sqrt(num))):
        if num%2 == 0:
            pos =False
            break
            
    return pos
 
def solution(numbers):
    prime = set()
    number = list(numbers)
    numbers=[]
    
    for n in range(1,len(number)+1):
        
        numbers.extend( list(permutations(number,n)))
    for i in range(len(numbers)):
        num =''
        for j in range(len(numbers[i])):
            num +=numbers[i][j]
        prime.add(int(num))
    answer = 0
    
    
    for num in prime:
        if num in[2,3]: answer +=1
        if num>=4:
            sqrt_n=int(math.sqrt(num))
            pos =True
            for d in range(2,sqrt_n+1):
                
                if num % d == 0:
                    pos=False
                    break
            if pos==True:
                
                answer+=1
    
        
    return answer