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

풀이 과정

• 1. 숫자의 범위는 최대가 7 자릿수. 소수를 구해야하므로 일단 check 리스트에 에라스토테네스의 체를 활용해 먼저 소수를 거른다.

check = [0]*10000000
check[0] = 1
check[1] = 1
for i in range(2,10000000):
    if check[i] == 0:
        for j in range(i*2,10000000,i):
            check[j] = 1

• 2. 브루트포스로 하다보면 숫자가 겹칠 수 있으므로 list가 아니라 set 를 사용한다. answer = set()
• 3. itertools의 퍼뮤테이션을 사용해서 모든 경우의 수를 구하고, 구해진 수에서 check 리스트에 소수로 판별이 되 있는 수를 answer에 추가한다.

from itertools  import permutations
for i in range(len(numbers)):
    for pro in permutations(numbers,i+1):
        n = int(''.join(pro))
        if check[n] == 0:
            answer.add(n)

• 4. answer의 길이 return return len(answer)

코드 전문

def solution(numbers):
    check = [0]*10000000
    check[0] = 1
    check[1] = 1
    for i in range(2,10000000):
        if check[i] == 0:
            for j in range(i*2,10000000,i):
                check[j] = 1
    answer = set()
    from itertools  import permutations
    for i in range(len(numbers)):
        for pro in permutations(numbers,i+1):
            n = int(''.join(pro))
            if check[n] == 0:
                answer.add(n)
    return len(answer)