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

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

 

코딩테스트 연습 - 소수 찾기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

문제 설명

 

 

주어진 문제의 설명 및 입출력

 

• 주어진 숫자는 문자열로 주어진다
  • 문자열로 주어진 숫자를 하나씩 나눠서 리스트로 변경한다
• 주어진 숫자를 한자리 숫자로 변경한 뒤 순열을 사용해서 만들 수 있는 숫자 문자열을 만든다
  • 해당 문자열을 만들고 set의 성질을 사용해서 중복 값 제거
• 만들어진 문자열의 경우 [ [" 0 " , " 1 " , " 1 " ] ]의 형태로 존재하기에 join 메서드를 통해 리스트의 문자열을 하나로 묶어준다
  • 숫자이기에 0으로 시작하는 경우는 없어야한다. 그렇기에 011 같은 경우 해당 문자의 첫 번째가 0이라면 문제풀이 리스트에 append를 하지 않는다
  • 또한 소수이기에 1이상의 수만 append를 한다.
• 에라스토테레스 체, 소수 판별을 사용
  • for 반복문을 사용하여 만들어진 tf 배열을 통해 해당 수가 소수인지 아닌지 판별한다.
  • 만약 주어진 tf의 배열이 True라면 해당 인덱스의 배수의 인덱스를 가진 리스트의 값은 False로 변경한다.

 

풀이 코드

 

import itertools

def solution(numbers):
    answer = 0
    num = [ i for i in numbers]
    num1 = []
    for i in range(1, len(numbers)+1):
        num1+=itertools.permutations(num,i)
    num1 =list(set(num1))
    num2=[]
    for i in num1:
        a=''.join(i)
        if int(a) >1 and a[0]!='0':
            num2.append(int(a))
            
    tf = [True]*(max(num2)+1)
    
    for i in range(2, max(num2)+1):
        if tf[i] == True:
            for j in range(i*2,max(num2)+1,i):
                tf[j]=False
    cnt = 0
    for i in num2:
        if tf[i]==True:
            cnt+=1
    return cnt