소수 구하기 - 에라토스테네스의 체(응용하여 완전탐색 소수찾기 문제 풀기)

코딩테스트에서 소수를 구하는 문제가 나올 경우 이 포스팅을 참고하여 코드를 작성하면 보다 효율적으로 작성할 수 있다.

소수란? 

2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수

 

에라토스테네스의 체 알고리즘

1 - 2부터 N까지의 모든 자연수를 나열한다.

2 - 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.

3 - 남은 수 중에서 i의 배수를 모두 제거한다(i는 제거하지 않는다).

4 - 더이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다.

 

*파이썬에서 제공해주는  sqrt함수를 응용할 예정

해당 숫자가 소수인지 아닌지는 제곱근까지만 확인하면 된다. 어차피 약수는 대칭을 이루기 때문이다.

 

import math

n = 1000
array = [True for i in range(n+1)]

for i in range(2,int(math.sqrt(n)+1)):
  if array[i] == True:
    j = 2
    while i*j <=n :
      array[i*j] = False
      j+=1
for i in range(2,n+1):
  if array[i]:
    print(i,end = ' ')

에라토스테네스의 체는 동빈나님의 이것이 취업을 위한 코딩테스트다 책을 참고하여 작성한 포스팅 입니다.

---

이를 활용하여, 아래 문제를 같이 풀어보도록 하겠습니다.

 

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

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

입출력 예

numbersreturn

17	3
011	2

입출력 예 설명

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

---

 

from itertools import permutations
def solution(n):
    a = set()#비어있는 집합자료형을 만듬
    for i in range(len(n)):#만들 수있는 숫자의 자리수는 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)

1)만들 수 있는 숫자의 조합을 모두 구한다.

2)소수만 걸러낸다.

 

• from itertools import permutations 

itertools는 파이썬에서 반복되는 데이터를 처리하는 기능을 포함하고 있는 라이브러리이다.

그 중에서도 우리는 순열의 기능을 사용하기 위해 permutation()함수를 사용할거다!

 

• for i in range(len(n)):

n값을 받고,  만들 수 있는 최대 숫자자리수는 n의 길이와 같을 것이다.

ex) "123" --> 만들 수 있는 숫자자리수는 3자릿수

 

•  a |= set(map(int, map("".join, permutations(list(n), i+1))))#합집합 이용하기

permutation()함수를 사용하여, n의 길이만큼 순차적으로 순열을 구한다.

ex) "123" -->   "1","2","3"     /       "12","21","13","31","23","32"       /         "123","213" .............

합쳐놓은 문자열을 int형으로 변환한다.

 

•  a -= set(range(0, 2))

기본적으로 0,1은 소수에 포함되지 않기때문에 0~1까지의 수를  a에서 제거해준다.

 

• for i in range(2, int(max(a) ** 0.5) + 1):
          a -= set(range(i * 2, max(a) + 1, i))

이부분이 바로 에라토스테네스의 체 를 이용한 부분이다.

2의 배수부터 없앨 예정이니 2부터 시작해서 최대값의 제곱근까지 i값을 증가 시킨다.

제곱근까지만 보는 이유는 자연수의 약수가 가지는 특징을 생각하면 된다.

예를들어 16이라는 자연수가 가진 약수는 다음과 같다.

 

1,2,4,8,16

이때 모든 약수에 대하여, 가운데 약수를 기준으로 하여 대칭적으로 2개씩 앞뒤로 묶어서 곱하면 16을 만들 수 있다.

즉 가운데 약수까지만 나누어 떨어지는지만 보면 된다는 말이다.

 

파이썬에서는 math란 라이브러리에서 math.sqrt()함수도 제공해주고 있으니 적절히 활용하면 된다.

int(max(a) ** 0.5) 를 int(math,sqrt(max(a)) 로 바꿔도 된다.

이렇게하면 시간 복잡도(O(X(1/2승))로 줄어든다.

 

이렇게 해당하는 제곱근까지 의 각각의 배수를 반복 제거하여 a에 소수만 남을 수 있도록 해준다.