오일러 프로젝트 51

E051.py

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**(n-4), 10**(n-3)):
        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()

E051.swift

//  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 (2...n).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: limit-1)
  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 (0...c).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] ? 1...9 : 0...9) {
    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(n-4)))
  let upperBound = Int(pow(10, Double(n-3)))
  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 4...7 {
    if test(i) { break }
  }
}

func timeit(_ f:() -> ()) {
  let s = Date()
  f()
  print("time: \(s.timeIntervalSinceNow * -1000)")
}

timeit(main)
print(mk)