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

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

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

 

조합을 전부 구해서 최대값에 대한 에라토스테네스의 체를 사용후 조합을 전부 읽어서 소수일 경우 카운터를 증가시켰다.

 

 

from itertools import permutations
import math

def prime_number(n):
    arr = [True]*(n+1)
    for i in range(2,int(math.sqrt(n)+1)):
        if arr[i] == True:
            j = 2
            while i*j <= n:
                arr[i*j] = False
                j += 1
    return arr



numbers="1239875"
s=[]
for i in numbers:
    s.append(i)

arr=[]
for i in range(1,len(s)+1):
    arr.append(list(permutations(s,i)))

result=[]
for i in arr:
    for j in i:
        a=""
        for k in j:
            a += k
        if int(a) not in result:
            result.append(int(a))

arr2=prime_number(max(result))


cnt = 0
for i in result:
    if i>1 and arr2[i] == True:
        cnt += 1

print(cnt)

numbers를 좀 높은수로 설정해봤다.

 

효율이 개꾸진거같은데 다른 풀이방법도 봐야겠다.