[python] 소수 찾기

인증사진(2024-09-01)

문제

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

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

답

from itertools import permutations

def solution(numbers):
    r = []  # 소수를 저장할 리스트 초기화
    for i in range(1, len(numbers) + 1):  # 숫자 조합의 길이를 1부터 시작하여 전체 길이까지 반복
        for j in permutations(list(numbers), i):  # 주어진 숫자들의 모든 순열 생성
            jj = int(''.join(j))  # 순열을 문자열로 결합한 후, 정수로 변환
            # jj가 소수인지 판별하는 과정
            for k in range(2, jj):  # 2부터 jj-1까지 나눗셈을 시도
                if jj % k == 0:  # 나누어 떨어지는 경우, 소수가 아님
                    break
            else:
                # 소수일 때 (반복문이 break되지 않고 끝났을 때)
                if jj not in r and jj != 0 and jj != 1:  # 이미 리스트에 없는 소수이며, 0과 1이 아닌 경우
                    r.append(jj)  # 리스트에 소수 추가
    return len(r)  # 발견된 소수의 개수 반환

 

추가공부

itertools.permutations : 주어진 숫자 조합을 이용하여 가능한 모든 숫자 조합을 생성하기 위해 사용