"소수찾기" 문제

프로그래머스 문제 링크

풀이

사용 언어 : python

permutations()

순열이란?
n개의 원소를 중 r개를 선택하여 순서를 고려하여, 중복 없이 뽑을 경우의 수이다.
itertools의 permutations()을 사용하여 순열을 구할 수 있어요!
그 외 itertools 알아보기

에라토스테네스의 체

소수를 판별하는 알고리즘이다.
어떤 수의 소수여부를 확인할 때는 그 수의 제좁근 까지만 약수를 검증하면 된다.
예시
위키백과

def prime_list(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n
    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False
    # 소수 목록 산출
    return [i for i in range(2, n) if sieve[i] == True]

코드

from itertools import permutations


def solution(numbers):
    numbers = list(numbers)
    number = set() # 중복 제거하기 위해
    for i in range(1, len(numbers)+1):
        number.update(
            list(map(int, list(map(''.join, permutations(numbers, i))))))
    num = list(number) #리스트로 변환
    answer = []
    for x in num:
        if x >= 2: # 0과 1은 소수가 아니라서
            check = True
            for i in range(2, int(x**0.5)+1):
                if x % i == 0: # 하나라도 나누어 떨어지는게 있으면 소수가 아니다!
                    check = False
                    break
            if check: # check가 True면 소수이므로 answer에 추가
                answer.append(x)
    return len(answer)