오일러 프로젝트 41

오일러 프로젝트 41 번은 n자리 소수이면서 1-n 팬디지털 소수인 것들 중에서 가장 큰 소수를 찾는다. 이는 의외로 매우 쉽게 찾을 수 있다. 

1부터 n까지의 숫자를 하나씩만 써서 만든 n자리 숫자를 팬디지털(pandigital)이라고 부릅니다. 2143은 4자리 팬디지털인데, 이 수는 동시에 소수이기도 합니다. n자리 팬디지털 소수 중에서 가장 큰 수는 무엇입니까?  (http://euler.synap.co.kr/prob_detail.php?id=41)

접근

9자리 팬디지털 숫자는 1~9의 숫자 조합으로 이루어져있으므로 각 자리 숫자를 모두 더하면 45가 되어 3의 배수가 된다. 따라서 모든 9자리 팬디지털 숫자는 소수가 될 수 없다. 같은 이유로 1-8 팬디지털 숫자의 자리수 합은 36이 되어 해당 사항 없다. 결국 7자리 이하의 팬디지털 숫자가 대상이 된다.
또한 7654321 부터 1씩 내려갈 필요없이, 순열을 이용해서 팬디지털 숫자만 검사하면 7! (5040)가지 후보에 대해서만 검사하면 되므로 범위를 크게 줄일 수 있다.

파이썬 풀이

itertools.permutations 를 이용해서 순열을 생성하고, 이렇게 생성된 숫자 리스트를 정수로 정리해서 소수인지 검사한다. [7,6,5,4,3,2,1]  로부터 순열을 생성하면 큰 값부터 작은 값으로 숫자가 만들어지므로 최초로 발견된 소수가 답이된다.

from functools import reduce
from itertools import permutations
def is_prime(n):
 if n < 2: return False
 if n in (2, 3): return True
 if n % 2 is 0 or n % 3 is 0: return False
 if n < 10 : return True
 l, k = n**0.5, 5
 while k <= l:
   if n % k is 0 or n % (k+2) is 0: return False
   k += 6
 return True
def e41():
  for i in permutations((7,6,5,4,3,2,1)):
    j = reduce(lambda x, y: 10*x + y, i)
    if is_prime(j):
      print(j)
      break
%time e41()
## Wall time: 3ms

Swift 풀이

Swift의 표준 라이브러리에는 순열을 생성하는 함수가 없으므로, 지난 문제에서 만들었던 함수를 사용해서 풀이한다.

import Foundation
func isPrime(_ n: Int) -> Bool {
  if n < 2 { return false }
  if (2...3) ~= n { return true } 
  if n % 2 == 0 || n % 3 == 0 { return false }
  if n < 10 { return true }
  let l = Int(sqrt(Double(n)) + 0.5)
  var k = 5
  while k < l {
    if n % k == 0 || n % (k + 2) == 0 { return false }
    k += 6
  }
  return true
}
let fatorial: (Int) -> Int = { ($0 < 2) ? 1 : (1...$0).reudce(1, *) }
func permutations<A> (_ n: Int, _ arr: [A]) -> [A] {
  var xs = arr
  let l = factorial(xs.count - 1)
  let (q, r) = (n / l, n % l)
  let a = xs.remove(at: q)
  return [a] + permutations(r, xs)
}
main: do {
  let q = [7,6,5,4,3,2,1]
  var k = 0
  let fold: (Int, Int) -> Int = { $0 * 10 + $1 }
  while true {
    let x = permutations(k, q)
    if isPrime(x) { print(x); break }
    k += 1
  }
}
// 대략 1~3 ms