[Python] 소수 찾기

1. 문제

 

 

 

2. 풀이 과정

방법 1) for문으로 자신보다 작은 수로 나눠지는지 하나씩 검사하여 소수를 판별하였다.

def prime(n): #소수여부 검사
    if n <= 1:
        return False
    for i in range(2, n):
        if n%i==0:
            return False
    return True

from itertools import permutations
def solution(numbers):
    answer = 0
    temp = set()#중복체크용 집합
    for i in range(1, len(numbers)+1):
        ps = permutations(numbers, i)
        for p in ps:
            su = int(''.join(p))
            if su not in temp and prime(su): #중복이 아니고 소수일 때
                answer += 1
            temp.add(su)
        
    return answer

 

방법 2) 에라토스테네스의 체 활용, 방법 1)보다 효율적이다.

from itertools import permutations
def solution(numbers):
    answer = 0
    su = set()
    #가능한 모든 경우를 정수형으로 저장
    #집합을 이용해서 중복 제거
    for i in range(1, len(numbers)+1):
        su |= set(map(int, map(''.join ,permutations(numbers, i))))
    
    su -= set(range(2)) #0, 1 제거
    
    #에라토스테네스의 체
    for j in range(2, int((max(su)**.5)+1)):
        su -= set(range(2*j, max(su)+1, j))
        
    return len(su)