[프로그래머스-완전탐색] 소수 찾기_파이썬 ❌⭕(에라토스테네스의 체)

programmers.co.kr/learn/courses/30/lessons/42839

코딩테스트 연습 - 소수 찾기

---

소수를 구하려면 어떻게 해야할까?

해당 수보다 작은 모든 수를 나누어 보면 된다.

n=100

def prime(a):
  if a < 2:
    return False
  for i in range(2, a):
    if a % i == 0:
      return False
  return True

for i in range(n + 1):
  if prime(i):
    print(i)

무식한 방법이지만, 직관적이고 확실해보인다. 그렇다면 더 효율적인 방법이 있을까?

있다. 에라토스테네스의 체를 활용하면 된다.

 

• 에라토스테네스의 체 : 범위에서 합성수를 지우는 방식으로 소수를 찾는 방법
  1. 1은 제거
  2. 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다.
  3. 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다.
  4. (반복)

n=1000
a = [False,False] + [True] * (n - 1)
primes=[]

for i in range(2, n+1):
  if a[i]:
    primes.append(i)
    for j in range(2 * i, n+1, i):
        a[j] = False
print(primes)

---

그렇다면 이제 문제를 풀어보자. 먼저 직관적으로.

from itertools import permutations
import math
def solution(numbers):
    def check(num):
        if num < 2:
            return False

        num_sqrt = math.sqrt(num)
        for i in range(2, int(num_sqrt) + 1):
            if num % i == 0:
                return False

        return True

    numbers = permutations([n for n in numbers], len(numbers))

    temp = set()
    for number in numbers:
        string = ''
        for num in number:
            string += num
            temp.add(int(''.join(string)))

    count = 0    
    for t in temp:
        if check(t):
            count += 1

    return count

permutations를 이용해 주어진 numbers로 가능한 모든 경우의 수를 temp 변수에 집어넣었다.

이 때, 중복처리를 해줘야 하므로 집합 자료형을 사용했다.

그리고 나서 check 함수를 통과시키면 성공적으로 해결할 수 있다.

 

이제 내 허접한 코드를 봤으니, 모범적인 코드를 살펴보자.

---

from itertools import permutations


def solution(numbers):
    primes = set()
    
    for i in range(len(numbers)):
        primes |= set(map(int, map(''.join, permutations(numbers, i+1))))
    
    primes -= set(range(2))
    
    for i in range(2, int(max(primes)**0.5)+1):
        primes -= set(range(i*2, max(primes)+1, i))
    
    return len(primes)

처음에 연산자 '|=' 가 나를 당황하게 했다. 아래 표를 보면 어떤 용도로 쓰는지 알 수 있을 것이다.

 

출처 : https://dojang.io/mod/page/view.php?id=2460

이 풀이는 합성수를 지우는 방식으로 소수를 찾는다. 즉 에라토스테네스의 체를 활용하는 것이다.

우선 모든 경우의 수에서 0과 1을 삭제하고, 그 뒤에는 최댓값의 제곱근 이하인 수들의 배수를 모두 삭제한다.

제곱근 이상의 수로 나누면 어짜피 나눌 수 없기 때문에 검사할 필요가 없다.

X ** 0.5 는 X의 제곱근을 의미한다.

모든 합성수를 제외하면 최종적으로 len(primes)이 만들 수 있는 소수의 수가 된다.