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

내가 푼 방법

1. permutations 이용해서 가능한 모든 경우 구하기
2. 2 ~ 경우의 수-1 까지 모든 수로 경우의 수의 나머지가 0인지 아닌지 확인해 소수 판별

from itertools import permutations

def solution(numbers):
    answer = 0
    all_nums = []

    for i in range(1, len(numbers)+1):
        all_nums.append(list(map(''.join, permutations(numbers, i))))

    all_nums = sum(all_nums, [])
    all_nums = list(set(map(int, all_nums)))

    for num in all_nums:
        if num == 2:
            answer += 1

        for j in range(2, num):
            if num % j == 0:
                break
            if j == num-1:
                answer += 1

    return answer

효율 좋은 풀이

• 에라토스테네스의 체 방법을 이용
  이 방법이 가장 효율적인 것은 알고 있었으나 막상 적용이 어려워 이렇게 풀지 못했음.

from itertools import permutations

def solution(numbers):
    answer = 0
    a = set()

    for i in range(len(numbers)):
        # a에 계속 넣어주되, 중복 허용 안하기 = 합집합 기호 사용
        a |= set(map(int, (map("".join, permutations(list(numbers), i+1)))))

    # 0, 1 은 제외    
    a -= set(range(0, 2))

    # 가장 큰 수의 제곱근을 구해서 그 수 +1 까지 나열
    for i in range(2, int(max(a) ** 0.5)+1):
        #에라토스테네스의 체를 이용해 소수 제거
        # i*2부터 배수들 계속 빼주기
        a -= set(range(i*2, max(a)+1, i))

    return len(a)

이 풀이에서 배울 수 있는 점

1. 굳이 list 사용 안 하고 어차피 항상 중복 허용 안하니까 set 형태로 계속 사용해도 됨
2. 문자열로 permutation하면 나처럼 이중리스트로 추가되니까 그냥 list(numbers)해서 list로 바꿔줌
3. 합집합 기호와 -=로 set에 계속 추가 및 제거 가능
4. 에라토스테네스 체 구현 방법

문제를 풀면서 배운 것들

1. itertools의 permutations

• permutation : 순열 -> 순서에 따라 다른 수로 포함됨
• combination : 조합 -> 순서 상관 x. 같은 수로 생각되어 포함 x

2. 이중리스트를 1차원으로 만들기
   -> sum(list_name, []) 이용