Notion에서 작성한 글이라, 여기에서 더 깔끔하게 보실 수 있습니다! 😮😊

---

[Challenger] 소수 찾기

[소수 찾기]

문제를 푸는 방법은 크게 아래의 두 단계로 나뉜다.

순열 생성

• 가장 쉬운 방법은 역시 라이브러리를 이용하는 방법이다.
  • from itertools import permutations
• 직접 구현해 보았다. p를 단순히 append해주면 참조가 계속 append 되어서, p가 변경될 때마다 ret에 저장된 모든 값들이 동일하게 변경되는 문제가 발생했다. Shallow Copy로 해결했다.

  def permutations(iterable, r):
      p = [0]*r
      used = [False]*len(iterable)
      ret = []
  
      def _perm(k):
          if k == r:
              ret.append(p[:])
              return
          for i in range(len(iterable)):
              if not used[i]:
                  p[k] = iterable[i]
                  used[i] = True
                  _perm(k+1)
                  used[i] = False
  
      _perm(0)
  
      return ret

각각 판별 vs 소수 목록 만들어 놓고 판별

• 하나의 수에 대해 소수 판별을 하는 것이 아닌, 최대 $7!$개의 수에 대해 소수를 판별하는 것이므로, 다음 두 가지 방법을 생각해볼 수 있다.
  1. $\sum_{k=1}^{n} P(n, k)$개의 수에 대해 소수 판별 $O(\sum_{k=1}^{n} P(n, k) \cdot \sqrt m)$
     • 동일한 수(이미 소수인지 판별했던 수)에 대해 중복된 소수 판별이 발생할 수 있다.(numbers의 각 자리가 unique하지 않을 때)
       • set을 이용하여 판별했던 수를 저장해 놓으면 중복되는 함수 호출을 피하는 방식으로 최적화할 수 있다.
     • 이 방법은 일단 소수인지 판별한 다음, 이미 계산했던 값인지 확인하는 방법에 비해 numbers의 각 자리가 unique하지 않을 때 더 빠르다.
     • 시간복잡도를 생각해 보자.
       • 최악의 경우는 numbers의 길이가 7이고, 각 자리가 unique해서 순열 생성 시 중복되는 숫자가 나오지 않는 경우이다. $\frac {1}{6} \cdot \sqrt {9876543} \approx 523.78$이므로 $O(\sum_{k=1}^{n}P(n, k) \cdot 524) = O(13699 \cdot 524)$인데, 각 숫자가 소수인지 판별하는 데에 최악의 단 한 경우에서만 $\frac {1}{6} \cdot \sqrt {9876543}$이고, 이후 $O(1)$까지 줄어들게 되므로 실제 시간복잡도는 훨씬 낮다고 볼 수 있다.
  2. sieve of eratosthenes로 소수 목록을 만들어 놓고 각 수에 대해 $O(1)$로 판별 $O(m \lg \lg m + \sum_{k=1}^{n}P(n, k))$
     • numbers를 이용하여 만들 수 있는 가장 큰 수까지의 소수 목록을 만들어 놓으면, 각 수에 대해 $O(1)$로 판별할 수 있게 된다.
     • 시간복잡도를 생각해 보자.
       • 최악의 경우는 numbers가 '9999999'인 경우이다. 이 때 소수 목록을 만드는 데 $O(9999999 \lg \lg 99999999) \approx O(45393753)$이 소요되고, 각 수에 대해 $O(1)$로 판별하므로 $O(45393753+13699)$이다.
• 따라서 각각의 수에 대해 판별하는 방법이 실행시간 면에서 훨씬 유리하다고 생각하여, 각각 판별하는 방법을 이용했다.

소수 판별 방법

1. $O(n)$ 소수 판별

   def isprime(x):
       if x <= 1: return False
       for i in range(2, x):
           if x%i == 0: return False
       return True

   • 소수의 정의를 활용한 소수 판별이다. 구간 $[2, n-1]$에 인수가 존재하면 합성수로 판단하여 0을 return한다.

2. $O(\sqrt n)$ 소수 판별

   def isprime(x):
       if x <= 1: return False
       for i in range(2, int(x**.5)+1):
           if x%i == 0: return False
       return True

   Proof.

   자연수 $n$을 $n= p \times q$ ($p \le q$, $p$와 $q$는 $1$과 $n$이 아닌 자연수) 를 만족하는 합성수라고 하자.

   $p \times q \le q \times q$이므로 $n \le q^2$이고 $\sqrt{n} \le q$ 이다. (∵ $n \in \mathbb{N}$)

   따라서 $q$의 최솟값이자 $p$의 최댓값은 $\sqrt n$이 되므로, $\sqrt n$까지만 확인하면 $n$이 소수인지 아닌지 판별할 수 있다. $\blacksquare$

3. $O(\frac{1}{6}\sqrt{n})$ 소수 판별

   def isprime(x):
       if x <= 1: return False
       if x <= 3: return True
       if x%2 == 0 or x%3 == 0: return False
       i = 5
       while i*i <= x:
           if x%i == 0 or x%(i+2) == 0: return False
           i += 6
       return True

   • $2$와 $3$을 제외한 모든 소수는 $6k \pm 1$ 꼴임을 이용한다.
   • $2$의 배수이거나 $3$의 배수인 경우까지 $O(1)$에 return하고,
   • 그 이후에는 $6k \pm 1$인 수로 나누어보면서 소수인지 판별한다.
     • 이 때, $i=5$부터 시작하는 이유는,
     • $i=6$ 또는 $i=7$로 시작할 경우 while i*i <= x: 때문에 구간 $(5, 49)$ 에서 소수를 정확히 판별하지 못하는 경우가 발생한다. (while문을 수정해주면 되긴 한다.)

4. Miller-Rabin 소수 판별

   • $n$이 작을 경우엔 $O(\frac{1}{6} \sqrt{n})$ 방법이 더 빠르기도 하고, 아직 부족해서… 정수론적 지식을 차근차근 더 쌓고 도전해 보겠다…!!

Solution 1. 순열 만들고 각각 판별 $O(\sum_{k=1}^{n}P(n, k) \cdot \frac{1}{6}\sqrt{n})$

def isprime(x):
    if x <= 1: return False
    if x <= 3: return True
    if x%2 == 0 or x%3 == 0: return False
    i = 5
    while i*i <= x:
        if x%i == 0 or x % (i+2) == 0: return False
        i += 6
    return True

def solution(numbers):
    checked = set()
    
    for n in range(1, len(numbers)+1):
        perm = permutations(numbers, n)
        for p in perm:
            num = int(''.join(p))
            if num not in checked and isprime(num):
                checked.add(num)
    
    return len(checked)

• permutations를 통해 만들어진 어떤 수는, 위에서 서술했듯 중복된 값이 존재할 수 있다. 따라서 계산했던 값은 set에 저장해놓고, 매 수에 대해 이미 계산했던 값은 아닌지 Amortized $O(1)$에 확인한 다음 소수 판별을 진행하는 방법으로 최적화했다.
• 상대적으로 오래 걸리는 TC #5에서 8.36ms, 10.4MB, TC #8에서 6.51ms, 10.4MB 의 결과가 나왔다.

Solution 2. sieve of eratosthenes $O(m \lg \lg m + \sum_{k=1}^{n}P(n, k))$

def get_primes(num):
    n = int(''.join(sorted(num, reverse=True)))
    primes = [True]*(n+1)
    primes[0] = primes[1] = False
    for i in range(2, int(n**.5)+1):
        if primes[i]:
            j = 2
            while i*j <= n:
                primes[i*j] = False
                j += 1
    
    return primes

def solution(numbers):
    checked = set()
    primes = get_primes(numbers)
    
    for n in range(1, len(numbers)+1):
        perm = permutations(numbers, n)
        for p in perm:
            num = int(''.join(p))
            if primes[num]: checked.add(num)
    
    return len(checked)

• 일반적인 sieve of eratosthenes의 구현이다. 만들 수 있는 가장 큰 수까지의 소수 목록인 primes를 만들어 놓고, permutations 를 통해 만들어진 어떤 수에 대해 소수인지 $O(1)$에 판별한다.
• sieve of eratosthenes의 경우 소수 목록의 공간복잡도가 $O(n)$이므로, 메모리 제한이 넉넉하지 않다면 다른 방법을 고려해봐야 한다.
• 상대적으로 오래 걸리는 TC #5에서 1039.46ms, 35.5MB, TC #8에서 1816.67ms, 52.5MB 의 결과가 나왔다.

Solution 2-2. improved sieve of eratosthenes $O(m \lg \lg m + \sum_{k=1}^{n}P(n, k))$

def get_primes(num):
    n = int(''.join(sorted(num, reverse=True)))
    sieve = [True]*(n+1)
    for i in range(3, int(n**.5)+1, 2):
        if sieve[i]: sieve[i*i::2*i] = [False]*len(sieve[i*i::2*i])
    
    return {2} | {i for i in range(3, n+1, 2) if sieve[i]}

def solution(numbers):
    primes = get_primes(numbers)
    ret = set()
    
    for i in range(1, len(numbers)+1):
        perm = permutations(numbers, i)
        for p in perm:
            num = int(''.join(p))
            if num in primes: ret.add(num)
    
    return len(ret)

• 개선된 sieve of eratosthenes의 구현이다. 모든 짝수는 소수가 아니므로 계산 자체에서 배제하기 위해 $i$ 가 $3$부터 시작하고, $2$ 간격으로 증가하여 모든 짝수에 대한 계산을 피한다.
• 그리고, 어떤 수 $i$에 대해 그의 배수들을 지워나갈 때, $i^2$보다 작은 $i$의 배수들에 대해서는 이전 반복에서 이미 지웠음이 자명하다. 따라서 $i$가 소수일 때, $i^2$부터 지워나감으로써 불필요한 계산을 최소화한다.
• 또, $i$는 홀수인 소수이므로, $i$의 배수 중 홀수는 $i \times i$, $i \times (i+2)$, $i \times (i+4)$, … 의 형태로 증가한다. (모든 짝수는 $2$의 배수로 이미 고려하지 않기 때문에 홀수 배수에 대해서만 지운다.) 이를 이용하면 간격을 $2i$로 설정할 수 있다.
• 문제에서는 소수인지 아닌지만 판별하면 되고, 그 순서가 중요하지 않으므로 Amortized $O(1)$에 판별할 수 있도록 set으로 만들어 반환한다.
• 상대적으로 오래 걸리는 TC #5에서 245.24ms, 65.7MB, TC #8에서 468.14ms, 105MB 의 결과가 나왔다.

---