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

사용 언어 - Python3

문제 - 소수찾기

프로그래머스

 

정답

순열조합 생성 후 소수 판별하는 완전 탐색 문제 (정답 맞춘 여부 X)

정답 풀이

1. numbers를 하나씩 자르기

nums = [n for n in numbers]

2. 순열조합 생성 list(permutations(nums,i))

3. 소수 판별 check True/False

4. set으로 중복 제거 후 개수 return

# 정답
from itertools import permutations

def solution(numbers):
    answer = []
    nums = [n for n in numbers]
    per = []

    for i in range(1,len(numbers)+1):
        per += list(permutations(nums,i))

    new_nums = [int(("").join(p)) for p in per]

    for n in new_nums:
        if n < 2:
            continue
        check = True
        for i in range(2,int(n**0.5)+1):
            if n%i == 0:
                check = False
                break
        if check:
            answer.append(n)

    return len(set(answer))

 

공부한 내용

 

1. permutations(list명, 원소개수) = 원소개수 만큼의 수열 만들기

permutations(nums,i) = 원소개수(i)를 변화시키면서 모든 가능한 수열 만들기

2. 소수 구하기

2보다 작은 0,1은 소수가 될 수 없다.

2부터 n의 제곱근까지 나눴을 때 나누어떨어진다면, 소수가 아니다. range(2,int(n**0.5)+1)

제곱근 값을 기준으로 왼쪽 값들에 약수가 존재하지 않는다면, 오른쪽에도 존재하지 않는다.

 

---

레퍼런스

• 정답 참고

[프로그래머스] 소수 찾기 (Level 2) / Python

• 소수 구하기

소수판별 알고리즘 - 파이썬 (Python)

• 순열과 조합

[Python 알고리즘] python으로 순열과 조합 직접 구현하기

• 깃허브 정답

GitHub - yyeongeun/codingtest: 코딩테스트 공부