프로그래머스 Level2 "소수 찾기"
문제
풀이
itertools의 permutations(순열)을 이용하여 글자를 조합하는 경우의 수를 찾아내고,
set 자료형을 이용하여 중복을 제거한다.
그 뒤 소수인지 판별하면 되는 문제!
에라토스테네스의 체
소수는 에라토스테네스의 체를 이용하여 구하였다.
0과 1은 소수가 아니니 제외하고 2부터 시작한다.
2를 소수에 추가하고 2의 모든 배수를 지우고 난 후,
3을 소수에 추가하고 지워지지 않은 3의 모든 배수를 지운다.
4는 이미 지워졌으므로 지나간다.
5는 지워지지 않았으므로 소수이며, 소수에 추가하고 5의 모든 배수를 지운다
.
.
.
이런 식으로 계속 반복을 진행하면 소수만이 남게 된다.
이를 에라토스테네스의 체라고 한다.
Python 코드
from itertools import permutations
def primeCheck(n):
# 에라토스테네스의 채를 이용한 소수 리스트를 반환하는 함수
checklist = [False,False] + [True]*(n-1)
primes=[]
for i in range(2,n+1):
if checklist[i]:
primes.append(i)
for j in range(i*2, n+1, i):
checklist[j] = False
return primes
def solution(numbers):
# itertools의 순열 메소드를 이용한 경우의 수 저장
sets = []
for i in range(1, len(numbers)+1):
sets += list(permutations(list(numbers), i))
# 문자열 이어 붙인 뒤 숫자로 자료형을 바꾸고
# set을 이용해 다시 한번 중복 제거 ('011'이 숫자형 11로 바뀌면서 생기는 중복 제거)
numlist = []
for x in sets:
temp = ''
for y in x:
temp += y
numlist.append(temp)
numlist = list(set(list(map(int, numlist))))
# 소수인지 확인
primetable = primeCheck(max(numlist))
answer = 0
for k in numlist:
if k in primetable:
answer += 1
return answer
Author And Source
이 문제에 관하여(프로그래머스 Level2 "소수 찾기"), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kgpaper/프로그래머스-Level2-소수-찾기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)