[PG] 42839 소수 찾기

[42839 Lv2]

me

from itertools import permutations
import math
def checkPrime(n): # 소수 찾기 - 에라토스테네스의 체를 사용하려 했으나 여러 수를 판별할 땐 별로라 해석 급히 우회함..
    n=int(n)
    print(math.sqrt(n),n**0.5)
    if n==0 or n==1: return False
    for i in range(2,int(n**0.5)):
        if n%i==0: return False
    return True
def solution(numbers): 
    answer = set()
    numbers=list(numbers)
    for i in range(1,len(numbers)+1):
        combs=list(permutations(numbers,i)) # i개수 만큼 순열 만들기
        for comb in combs: # 각 순열 마다 돌면서 문자열로 만들어주기
            num=''
            for c in comb:
                num+=c
            if checkPrime(int(num)): answer.add(int(num)) # 만든 문자열이 소수면 answer에 저장하기

    return len(answer) # 이때 answer은 set이기 때문에 중복을 거른 상태.
print(solution('17'))
print(solution('011'))

solution

from itertools import permutations
def solution(n):
    a = set()
    for i in range(len(n)):
        a |= set(map(int, map("".join, permutations(list(n), i + 1))))
    a -= set(range(0, 2))
    for i in range(2, int(max(a) ** 0.5) + 1):
        a -= set(range(i * 2, max(a) + 1, i))
    return len(a)

• 문자열 처리 방법
  • 모든 i+1 개수에 대해 순열을 가져와서 하나씩 문자열로 만든다.
  • 각 문자열을 int로 형변환한다.
  • set으로 중복 처리를 한다
  • | 연산자 : or 이자 합집합
• 에라토스테네스의 체를 한줄로 구현한거 보고 가져왔다.
  • 2부터 루트 max(a)까지 과정 반복
  • 2~max(a)까지 곱한 i의 배수를 set에 모음
  • - 연산자 : 차집합

여러 수를 판별할때는 에라토스테네스의 체가 안좋다 그래서 그냥 다른 거 썻는데, 지금 보니깐 왜 안좋은지도 모르면서 바꿔버린 나 자신이 아쉽다.
set를 잘 써야겠다는 생각도 많이 든다.