문제

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

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한 사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예시

아이디어

✅숫자를 각 2,3,...,len(numbers)개로 이루어진 조합 리스트를 구해 중복을 제거한다. 리스트의 값들을 하나씩 소수가 맞는지 확인한다.

1. numbers를 리스트로 변경한다.
2. 반복문과 permutations을 이용해서 2개부터 길이만큼의 개수의 조합을 만든다.
3. 튜플로 되어있는 리스트를 숫자를 합해 정수로 만든다음 중복을 제거한다.
4. num 리스트에 있는 숫자를 차례로 소수인지 판별한다.
   4.1 약수들은 서로 대칭되므로 소수인지 확인할 때, math.sqrt()를 이용한다.
5. 소수이면 answer을 하나 더해준다.

solution함수_python

import itertools, math

def solution(numbers):
    answer = 0
    numbers = list(numbers)
    num = []
    for i in range(1, len(numbers)+1):
        num += list(itertools.permutations(numbers,i))
    for i in range(len(num)):
        num[i] = int(''.join(list(num[i])))
    num = list(set(num))
    for i in num:
        if i >=2:
            chk = True
            for j in range(2,int(math.sqrt(i))+1):
                if i % j == 0:
                    chk = False
                    break
            if chk:
                answer+=1
  
    return answer

소수찾기 함수 참고 출처

다른사람 풀이

permutations을 list로 받아서 추가한 다음 join을 이용해 int로 바꾸는 과정을 한 줄로 간략하게 표현했다.
✔️map을 두 번 이용해 join하고 int로 변경한 다음 set을 이용하여 중복을 제거하고 | (OR)을 이용해 다른 길이의 조합일때도 중복을 제거했다.
✔️또한 집합으로 {0, 1}의 값을 차집합으로 빼주었다.
✔️에라토스테네스의 체를 이용하여 소수를 찾는다. 이 때, set을 이용하여 차집합으로 남은 a리스트의 길이를 반환하면 답이다.

from itertools import permutations
def solution(n):
    a = set()
    for i in range(len(n)):
        a |= set(map(int, map("".join, permutations(list(n), i + 1))))
    a -= set(range(0, 2))
    for i in range(2, int(max(a) ** 0.5) + 1):
        a -= set(range(i * 2, max(a) + 1, i))
    return len(a)

출처: 프로그래머스 다른사람 풀이

에라토스테네스의 체

범위에서 합성수를 지우는 방식으로 소수를 찾는 방법

1. 1은 제거
2. 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다.
3. 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다.
4. 지워지지 않은 수 중 제일 작은 5를 소수로 채택하고, 나머지 5의 배수를 모두 지운다.
5. (반복)
   

✅python으로 구현한 에라토스테네스의 체

n=1000
a = [False,False] + [True]*(n-1)
primes=[]

for i in range(2,n+1):
  if a[i]:
    primes.append(i)
    for j in range(2*i, n+1, i):
        a[j] = False
print(primes)

출처: https://wikidocs.net/21638