소수 찾기 (lv2)

 처음엔 에라토스테네스의 체로 소수 집합을 만들어 풀었는데, 정석으로 다시 풀었다. 전자보다 후자가 시간, 용량면에서 우세하다.

---

코드

에라토스테네스의 체

from itertools import permutations

def solution(numbers):
    answer = 0
    primeNumbers = eratosthenes(int(''.join(sorted(numbers, reverse=True))))
    s = set()
    for i in range(1,len(numbers)+1):
        s = s | set(map(lambda x : int(''.join(x)), permutations(numbers,i)))
    for v in s:
        if v in primeNumbers:
            answer += 1
    return answer

def eratosthenes(n):
    sieve = [True] * (n + 1)
    for i in range(2, int(n ** 0.5) + 1):
        if sieve[i] == True:
            for j in range(i+i, n+1, i):
                sieve[j] = False
    return set([i for i in range(2, n+1) if sieve[i] == True])

정석

from itertools import permutations

def solution(numbers):
    answer = 0
    s = set()
    for i in range(1,len(numbers)+1):
        for num in map(lambda x : int(''.join(x)), permutations(numbers,i)):
            if not num in s and num > 1:
                for i in range(2,int(num**0.5)+1):
                    if num % i == 0:
                        break
                else:
                    answer += 1
            s.add(num)
    return answer