태그: 오일러프로젝트

오일러 프로젝트 35 번 문제는 순환하는 소수에 대한 내용이다.

소수 중에서 각 자리의 숫자들을 순환시켜도 여전히 소수인 것을 circular prime이라고 합니다. 예를 들어 197은 971, 719가 모두 소수이므로 여기에 해당합니다. 이런 소수는 100 밑으로 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97 처럼 13개가 있습니다. 그러면 1,000,000 밑으로는 모두 몇 개나 있을까요?

http://euler.synap.co.kr/prob_detail.php?id=35

접근

먼저 순환하는 수를 어떻게 만들 수 있을까? (문자열로 변환) -> (앞글자를 떼어) -> (맨뒤에추가) -> (정수로변환) 하는 작업을 해도 되는데, 괜히 깔끔하지가 못하고 너저분한 느낌이다. 문자열의 개입없이 이걸 처리할 수 있을까? 10진수의 자리 숫자와 관련된 작업에는 로그(log)가 등장하면 된다. 예를 들어 423의 상용로그값은 약 2.6263인데, 여기서 정수 부분만 취해서 1을 더하면 423이 몇 자리 수인지를 알 수 있게 된다. 따라서 10으로 나눈 나머지와 몫을 가지고서 이 나머지에 원래 수의 상용로그의 정수부만큼 10을 거듭곱하여 더하면 끝자리 수를 앞으로 이동시킨 값이 된다.

from math import log10
a = 423
n = int(log10(a))
q, r = divmod(a, 10)
b = r * (10**n) + q
print(b) # 342

이 동작을 계산중에 나오는 n (자리수)만큼 반복해서 변환된 숫자가 소수인지를 판단하면 된다.

개선 포인트

성능 개선을 위한 포인트는 다음과 같다.

1. 모든 순환 버전을 소수인지 검사한다. 따라서 0, 2, 4, 6, 8 이 포함된 숫자라면 이 들 숫자가 1의 자리에 오는 시점에 짝수로서 검사를 통과못하게 된다. 이를 이용하면 빠르게 탈락여부를 결정할 수 있다.
2. 같은 원리로 5가 포함된 경우도 빠른 탈락
3. 당연한 이야기지만, 백만번의 (혹은 짝수는 거른다 생각해서 양보하면 50만번)의 루프를 돌 필요도 없다. 처음에 출발하는 수 자체가 소수여야하므로, 에라토스테네스의 체를 만들어서 소수집합에서 원소를 꺼내어 검사하면 된다.

순환하는 수를 만드는 건 쉽다. 자리수에 해당하는 10의 제곱수로 나눈 몫과 나머지를 가지고 나머지*10 + 몫으로 순환시킨다. 검사를 빠르게 하기 위해 소수채를 만들고 여기에 있나 없나를 검사한다.

from math import log10, floor

def prime_sieve(bound):

    sieve = [True] * (bound//2)
    for i in range(3, int(bound**.5)+1, 2):
        if sieve[i//2]:
            sieve[i * i // 2::i] = [False] * ((bound - i * i - 1) // (2 * i) + 1)
    return [2] + [2*i+1 for i in range(1, bound // 2) if sieve[i]]

def e35():
    def check(n):
        k = str(n)
        for c in "024568":
            if c in k:
                return False
        c = int(log10(n))
        l = 10**c
        m = n
        for _ in range(c+1):
            q, r = divmod(m, l)
            m = r * 10 + q
            if m not in s:
                return False
        return True

    s = set(prime_sieve(1000000))
    b = [2,5] + list(filter(check, s)) // 2, 5는 자리 숫자 검사에서 탈락하므로, 예외적으로 추가
    print(len(b))

%time e35()
# Wall time: 208 ms

보너스 : Swift 풀이

Swift에서 에라토스테네스 체를 만드는 부분과, 로그 연산등을 수행하는 부분을 살펴보자. 로그 연산은 Foundation을 통해서 C 라이브러리의 함수를 그대로 사용한다.

// Swift 4
import Foundation

// 소수체를 만들자
let limit = 999_999
let sieve: [Bool] = {
  var s = [false, false] + Array(repeating: true, count: limit)
  for k in 2...limit where s[k] {
    for j in stride(from: k*2, through: limit, by: k) { s[j] = false }
  }
  return s
}()

let isPrime: (Int) -> Bool = { sieve[$0] }
let primes = (0...limit).filter{ sieve[$0] }


func test(_ n: Int) -> Bool {
  // 먼저 글자로 체크한다.
  var n = n
  let s = String(n)
  for c in "024568" {
    if s.contains(c) { return false }
  }
  // 자리수 및 가장 앞자리로 옮기기 위해 필요한 값
  let c = floor(log10(Double(n)))
  let l = Int(pow(10, c))
  // 자리수를 돌려가며 검사한다.
  for _ in 0..<Int(c) {
    let (q, r) = (n / 10, n % 10)
    n = r * l + q
    if !isPrime(n) { return false }
  }
  return true
}    

main: do {
  let result = [2, 5] + primes.filter(test)
  print(result.count)
}