Programmers _ 소수찾기 _ 파이썬

📃 문제

프로그래머스 소수찾기

조건

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

알고리즘 - 완전탐색

에라토스테네스의 체 : 소수 찾기

1. 범위 내 전체 자연수를 저장한 배열만들기
2. 2부터 범위최댓값의 제곱근까지의 수로 반복문 (범위 내 모든 수를 돌릴 필요 없다 !!)
3. 반복문 도는 그 수의 배수인 값은 배열에서 지운다. (배수니까 소수가 될 수 없다)

n = 99 # 최대값 지정
allnum = set(range(2,n+1))
for i in range(2,int(n**0.5)+1):
    allnum -= set(range(i+i, n+1, i))
print(allnum)
# {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}

💡 풀이 과정

1) permutations, 에라토스테네스의 체 🥳

코드 설명 :
permutations 라이브러리를 이용하여 입력값으로 만들 수 있는 숫자 순열 생성.

from itertools import permutations

def solution(numbers):
    numbers = list(map(int, numbers))
    numli = []
    # 1~numbers길이 만큼의 자릿수를 가진 숫자 생성
    for i in range(len(numbers), 0, -1):
        p = permutations(numbers, i)
        for pi in p:
            numli.append(int(''.join(str(x) for x in pi)))        
    numli = list(set(numli))
    # 소수찾기 - 에라토스테네스의 체
    primeTF =[True] * (max(numli) +1)
    primeTF[1] = False
    for i in range(2,int((max(numli))**0.5)+1):
        if primeTF[i] == True:
            for j in range(i+i, max(numli)+1, i):
                primeTF[j] = False
    answer = 0
    # 에라토스테네스의 체로 구한 숫자들 중 소수인지 확인 후 카운트
    for i in (numli):
        if i!=0 and primeTF[i]:
            answer+=1
    return answer

자릿수 생성 for문을 굳이 역순으로 할 필요 없음.
중복제거 해야함 : "011" 이라면 세자리 수 만들때 101,101,110,110 이렇게 됨

수정 내용 :
집합을 이용하여 집합연산자(|)를 이용하여 차집합을 구할 수 있다. (중복제거)

def solution(numbers):
    numset = set()
    for i in range(len(numbers)):
        numset |= set(map(int, map(''.join, permutations(list(numbers), i+1))))
    numset -= set(range(0,2)) # 0과 1 제거 : 0과 1은 어짜피 소수가 아니니까.
    # 에라토느테네스의 체도 집합으 이용하여 간단히
    for i in range(2,int((max(numset))**0.5)+1):
        numset -= set(range(i+i, max(numset)+1, i))
    return len(numset)

🔍 정리 & 배운 것

set() 집합 형
중복을 허용하지 않는다
-> list(set(리스트)) 로 리스트 내 중복 제거
a = set() 로 선언 가능

집합은 순서가 유지 되지 않는다.
-> 연산 이후 순서가 처음과 같지 않다.

집합 연산자
합집합 | 혹은 union
집합을 업데이트 할땐 |= 이용
-> 업데이트 하는 값들 중 중복되지 않는 값만 들어옴

a = {1,2,'3'}

a |= {2,'4'}
print(a)		# {1, 2, '3', '4'}

값 추가 .add(값)
값 여러개 추가 .update([값,여,러,개])

연산 이후 본래 순서를 유지하고 싶다면
리스트를 이용하여 [x for x in a if x in b] 등