프로젝트 오일러 51

Swift 풀이

분량상, 소수 검사 함수나 순열 생성함수는 생략한다.

패턴으로부터 숫자 목록을 생성하는 함수

패턴은 [Bool] 타입이며, 여기에 n 자리 정수를 받아서 치환되는 숫자 목록을 생성하는 함수를 작성해보자.

  1. 패턴의 끝자리가 치환숫자 자리인 경우는 8개의 소수를 만들 수 없으므로 아예 빈 배열을 리턴한다.
  2. 주어진 숫자의 1자리 수가 끝에 오는 경우에도 짝수 혹은 5의 배수이면 미리 빈 배열을 리턴한다.

이 함수가 실질적으로는 상당히 많이 호출될 것이기 때문에1 여기서 이렇게 보초를 세워서 가능한 성능을 높여본다.  참고로 true 인 경우에는 치환숫자를 false 인 경우에는 고정 숫자에서 하나를 채운다.

func makeNumbers(pattern: [Bool], with n: Int) -> [Int] {
  // 주어진 정수를 고정숫자의 배열로 전환한다.
  let fixedNumbers:[Int] = {
    let c = Int(log10(Double(n)))
    return (0...c).map{ n / Int(pow(10, Double(c-$0))) % 10 }
  }()
  var temp:[Int] = [] // 결과 배열
  // 보초. 우선 맨끝자리가 치환자리면 실패
  if let last = pattern.last, last { return [] }
  // 정수값 1자리가 0,2,4,5,6,8이 아니어야 한다.
  if [0,2,4,5,6,8].contains(n % 10) { return [] }

  // 숫자를 만드는 구간
  for a in (pattern[0] ? 1...9 : 0...9) { // 첫자리가 치환영역이면 0은 올 수 없다.
    var (x, g) = (0, fixedNumbers.makeIterator())
    for b in pattern {
      x = x * 10 + (b ? a : g.next()!)
    }
    temp.append(x)
  }
  return temp
}

다음은 특정 자리수 구간을 검사하는 함수를 작성한다. 역시 별로 어려울 것 없다.

func test(_ n: Int) -> Bool {
  let lowerBound = Int(pow(10, Double(n-4)))
  let upperBound = lowerBound * 10
  var template = Array(repeating: false, count: n)
  (0..<3).forEach{ template[$0] = true }
  for k in lowerBound..<upperBound {
    for i in (0..<(factorial(n))) { // 템플릿 순열을 모두 검사
      let pattern = permutation(pattern, i)
      let numbers = makeNumbers(pattern: pattern, with: k)
      if !numbers.isEmpty && numbers.filter(isPrime).count == 8 {
        print(numbers.min()!)
        return true
      }
  }
  return false
}   

최종 결과

from itertools import permutations
limit = 100_0000
seive = [False, False] + [True] * (limit 1)
for i in range(2, int(limit**0.5)):
if seive[i]:
seive[i*2::i] = [False] * ((limit i) // i)
is_prime = lambda x: seive[x]
def make_template(n):
x = '0' * (n 3) + '111'
return permutations(x)
def make_numbers(k, template):
result = []
for i in range(10):
bucket = []
x = iter(str(k))
for j in template:
bucket.append(next(x) if j == '0' else str(i))
if bucket[0] != '0' and bucket[1] not in '024568':
result.append(int(''.join(bucket)))
return result if len(result) > 7 else []
def p51(n=6):
for k in range(10**(n4), 10**(n3)):
if k % 3 is 0:
continue
for template in make_template(n):
if template[1] == '1':
continue
groups = [x for x in make_numbers(k, template) if is_prime(x)]
if len(groups) == 8:
print(min(groups), groups)
return True
return False
def main():
for n in (4,5,6,7):
if p51(n):
return
%time main()

view raw
E051.py
hosted with ❤ by GitHub

// Write some awesome Swift code, or import libraries like "Foundation",
// "Dispatch", or "Glibc"
import Foundation
import Glibc
func factorial(_ n: Int) -> Int {
if n < 2 { return 1 }
return (2n).reduce(1, *)
}
func permutation<T>(_ list: [T], _ n: Int) -> [T] {
if n == 0 { return list }
var xs = list
let l = factorial(xs.count 1)
let (q, r) = (n / l, n % l)
let a = xs.remove(at: q)
return [a] + permutation(xs, r)
}
let sieve:[Bool] = {
let limit = 100_0000
var s = [false, false] + Array(repeating: true, count: limit1)
for i in 2..<(Int(sqrt(Double(limit))+0.5)) where s[i] {
stride(from:i*2,through:limit,by:i).forEach{ s[$0] = false }
}
return s
}()
let isPrime:(Int) -> Bool = { sieve[$0] }
func makeNumbers(pattern: [Bool], with n: Int) -> [Int] {
let fixedNumbers: [Int] = {
let c = Int(log10(Double(n)))
return (0c).map{ n / Int(pow(10, Double(c$0))) % 10}
}()
var temp:[Int] = []
if let last = pattern.last, last { return [] }
if [0,2,4,5,6,8].contains(n % 10) { return [] }
gen: for a in (pattern[0] ? 19 : 09) {
var x = 0
var g = fixedNumbers.makeIterator()
for b in pattern {
x = x * 10 + (b ? a : g.next()!)
}
temp.append(x)
}
return temp
}
func test(_ n: Int=6) -> Bool {
let lowerBound = Int(pow(10, Double(n4)))
let upperBound = Int(pow(10, Double(n3)))
var template = Array(repeating:false, count: n)
(0..<3).forEach{ template[$0] = true }
for k in lowerBound..<upperBound {
for i in (0..<(factorial(n))) {
let pattern = permutation(template, i)
let numbers = makeNumbers(pattern: pattern, with: k)
if !numbers.isEmpty && numbers.filter(isPrime).count == 8 {
print(numbers.min()!)
return true
}
}
}
return false
}
func main() {
for i in 47 {
if test(i) { break }
}
}
func timeit(_ f:() -> ()) {
let s = Date()
f()
print("time: \(s.timeIntervalSinceNow * -1000)")
}
timeit(main)
print(mk)

view raw
E051.swift
hosted with ❤ by GitHub

 


  1. 네자리수부터 체크하는 경우 답을 찾을 때까지 106,827회 호출된다.