Skip to content

Instantly share code, notes, and snippets.

@sooop

sooop/e051.swift

Last active January 12, 2016 04:01
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save sooop/97ed74acd9569a0ac6c5 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save sooop/97ed74acd9569a0ac6c5 to your computer and use it in GitHub Desktop.
Download ZIP
Project Euler on Swift # 005 (051~060) 5/10
Raw
e051.swift
#!/usr/bin/swift
/*
오일러 프로젝트 51번
두 자리 숫자 *3의 첫번째 자리를 여러가지로 바꿨을 때 가능한 아홉 가지의 결과 중에서 13, 23, 43, 53, 73, 83의 여섯 개는 소수입니다.
56**3 의 3번째와 4번째 자리를 동일한 숫자로 바꿔서 만들어지는 10개의 다섯자리 숫자 중에서는 아래에서 보듯이 7개가 소수가 되며, 이것은 이런 식으로 7개의 소수가 만들어지는 첫번째 경우입니다. 이 소수 집단의 첫번째 수인 56003은 이런 성질을 갖는 가장 작은 소수입니다.
56003, 56113, 56333, 56443, 56663, 56773, 56993
위의 예처럼 원래의 일부를 동일한 숫자로 치환했을 때 8개의 소수 집단이 만들어지는 경우를 찾고, 그 집단에 속한 가장 작은 소수를 구하세요.
치환하는 자리는 인접하지 않아도 되고, 가장 앞부분을 치환하는 경우 거기에 0은 올 수 없습니다.
조건
1. 맨 끝자리 수는 변하는 숫자여서는 안된다. (짝수나 5가 올 수 있으므로 8개의 소수를 만들 수 없다.)
2. 변하는 자리 숫자가 1개인 경우도 제외. 반드시 3의 배수가 나오게 된다.
3. 2와 같은 이유로 2, 4개의 경우도 제외된다. 변하는 숫자는 3의 배수 개가 되어야 한다.
4. 4자리 수의 경우 소수가 모두 1061개인데 이를 만족하는 8개 소수 그룹은 존재하지 않는다.
5.
*/
import Foundation
func timeit(@noescape f:() -> Void) {
let s = NSDate()
f()
let e = NSDate().timeIntervalSinceDate(s)
print("time: \(e * 1000) ms")
}
func isPrime(n: Int) -> Bool {
switch true {
case n < 2:
return false
case n == 2, n == 3:
return true
case n % 2 == 0, n % 3 == 0:
return false
case n < 9:
return true
default:
var k = 5
let l = Int(floor(sqrt(Double(n))))
while k <= l {
if n % k == 0 || n % (k + 2) == 0 {
return false
}
k += 6
}
return true
}
}
func countIn(l:Int, _ e:Int) -> Int {
// 주어진 정수 l 에서 숫자 e 가 몇개 들어있는지 센다.
return toArray(l).map{ $0 == e ? 1 : 0 }.reduce(0, combine:+)
}
func toArray(var n:Int) -> [Int] {
// 정수 n을 각자리 숫자의 배열로 변환한다.
var result = Array<Int>()
while n > 0 {
result.append(n % 10)
n = n / 10
}
return result.reverse()
}
func toInt(n:[Int]) -> Int {
// `toArray` 함수로 변환한 배열을 다시 정수값으로 변환한다.
var result = 0
for i in n {
result = result * 10 + i
}
return result
}
func changeWith(n:Int, _ d:Int) -> [Int] {
let a = toArray(n)
var result = Array<Int>()
func change(l:[Int], _ d:Int, _ s:Int) -> [Int] {
return l.map{ $0 == d ? s : $0 }
}
for i in 0...9 {
let t = change(a, d, i)
result.append(toInt(t))
}
return result
}
func test(n:Int, _ d:Int) -> Bool {
// n을 이루는 숫자중 d를 0, 1, 2, ...9까지 바꾸면서
// 6자리 소수가 8개인지 확인
let t = changeWith(n, d).filter{ $0 > 100000 && isPrime($0) }
return t.count == 8
}
timeit{
// 6자리 소수 대상으로
let sample = Array(100000...999999).filter(isPrime)
// 0, 1, 2 가 3개 있는 소수를 대상으로
// 이 숫자들을 모두 돌려본다.
func check(p:Int, _ d:Int) -> Bool {
let ld = p % 10
if countIn(p, d) == 3 {
if ld != d {
return test(p, d)
}
}
return false
}
for p in sample {
let ld = p % 10
switch true {
case check(p, 0),
check(p, 1),
check(p, 2):
print(p)
return
default:
continue
}
}
// 121313
// time: 754.709959030151 ms
}
Raw
e052.swift
#!/usr/bin/swift
/*
125874를 2배 하면 251748이 되는데, 이 둘은 같은 숫자로 이루어져 있고 순서만 다릅니다.
2배, 3배, 4배, 5배, 6배의 결과도 같은 숫자로 이루어지는 가장 작은 수는 무엇입니까?
*/
/**: # 풀이
순열인 두 수의 차는 항상 9의 배수이다. 이 때 2배 한 수가 순열이라는 것은 그 수가 9의 배수라는 의미.
같은 숫자가 자리를 바꿨을 때 그 차이는 10^x*A - 10^y*A 이므로 9의 배수이고, 모든 자리수에 대해서 합산했을 때도
같은 원리로 9의 배수만큼 차이난다.
또한 6번에 걸쳐서 반복될 수 있다는 것은 최소 6자리 이상의 수임을 의미한다.
따라서 99999 부터 9씩 증가하여 검사하는데 6자리의 경우에는 100_0000 / 6 까지 검사하면 된다.
만약 이 중에 답이 나오지 않는다면 999_999 ~ 10_000_000/6 사이를 다시 검사한다.
**/
//Swift 2.0
import Foundation
func timeit(@noescape f:()->()) {
let s = NSDate()
f()
let e = NSDate().timeIntervalSinceDate(s)
print("time: \(e*1000) ms")
}
func test(n:Int) -> Bool {
let a = Array(1...6).map{ String(String($0 * n).characters.sort()) }
let b = Set(a)
return b.count == 1
}
timeit{
for i in stride(from:99999, through:1000000/6, by:9){
if test(i) {
print(i)
break
}
}
}
//142857
//time: 1716.05497598648 ms
Raw
e053.swift
#!/usr/bin/swift
/*
1,2,3,4,5 다섯 숫자 중에서 세 개를 고르는 것에는 다음과 같은 10가지 경우가 있습니다.
123, 124, 125, 134, 135, 145, 234, 235, 245, 345
조합론이라는 분야에서는 이것을 5C3 = 10 이라고 표시하며, 일반적인 식은 아래와 같습니다.
nCr =
n!
r!(n−r)!
, 단 r ≤ n 이고, n! = n×(n−1)×...×3×2×1 이며 0! = 1.
이 값은 n = 23 에 이르러서야 23C10 = 1144066 으로 처음 1백만을 넘게 됩니다.
1 ≤ n ≤ 100 일때 nCr의 값이 1백만을 넘는 경우는 모두 몇 번입니까? (단, 중복된 값은 각각 계산합니다)
일단 팩토리얼은 숫자가 너무 커지니 직접 계산할 수 없고,
a * a - 1 * a - 2 .... * b + 1
-------------------------------
b * b - 1 * b - 2 .... * 1
이런 형태로 계산식이 정리되는데 분모는 항상 1로 약문되므로,
약분이 끝난 a 쪽 숫자들을 곱해서 nCr을 계산할 수 있다.
문제는 1~100 범위에서 이 값들을 계산할 때 최대값은 100891344545564193334812497256나
이므로, 일일이 계산하지 않고, 분자값들을 곱하는 과정에서 백만 이상인 경우에는
더이상 체크하지 않는다.
*/
import Foundation
func timeit(@noescape f:() -> Void) {
let s = NSDate()
f()
let e = NSDate().timeIntervalSinceDate(s)
print("time: \(e * 1000) ms")
}
func product(l: [Int]) -> Int? {
let limit = 999_999
var p = 1
for i in l {
p = p * i
if p > limit {
return nil
}
}
return p
}
func gcd(a: Int, _ b: Int) -> Int {
let (x, y) = a > b ? (a, b) : (b, a)
if y == 0 { return 1 }
if x % y == 0 { return y }
return gcd(y, x % y)
}
func abbr(var a: [Int], _ b: [Int]) -> Int? {
for k in b {
var x = k
var temp = a
for (i, y) in a.enumerate() {
let g = gcd(x, y)
if g > 1 {
x = x / g
temp[i] = y / g
}
if x == 1 {
break
}
}
a = temp
}
return product(a)
}
func nCr(n:Int, _ r:Int) -> Int? {
let result = abbr(Array(n-r+1...n), Array(1...r))
return result
}
func p053main(){
var count = 0
for i in 23...100 {
for j in 1...i {
if nCr(i, j) == nil {
count += 1
}
}
}
print(count)
}
timeit(p053main)
// 4075
// time: 2008.91500711441 ms
Raw
e055.swift
/*47이란 숫자를 골라서 뒤집은 다음 다시 원래 수에 더하면, 47 + 74 = 121 과 같이 대칭수(palindrome)가 됩니다.
물론 모든 숫자가 이토록 쉽게 대칭수를 만들어내지는 않습니다. 예를 들어 349의 경우,
349 + 943 = 1292
1292 + 2921 = 4213
4213 + 3124 = 7337
위에서 보는 것처럼 3번의 반복과정을 거쳐야 대칭수가 됩니다.
196과 같은 몇몇 숫자들은 이와 같은 과정을 아무리 반복해도 대칭수가 되지 않을 것이라고 추측되는데, 이런 수를 라이크렐 수 (Lychrel number) 라고 부릅니다. 아직 증명되지는 않았지만, 문제 풀이를 위해서 일단 라이크렐 수가 존재한다고 가정을 하겠습니다.
또한 1만 이하의 숫자들은, 50번 미만의 반복으로 대칭수가 되든지 라이크렐 수이든지 둘 중 하나라고 합니다.
1만을 넘어서면 10677에 이르렀을 때 비로소 53번의 반복으로 4668731596684224866951378664 라는 28자리의 대칭수가 만들어집니다.
그러면 1만 이하에는 몇 개의 라이크렐 수가 존재합니까?*/
//Swift 2.0
import Foundation
func timeit(@noescape f:()->()) {
let s = NSDate()
f()
let e = NSDate().timeIntervalSinceDate(s)
print("time: \(e*1000) ms")
}
func isPalindrome(s:String) -> Bool {
let cs = s.characters
let l = cs.count
var i1 = cs.startIndex
var i2 = cs.endIndex.predecessor()
for _ in 0..<l/2 {
if cs[i1] != cs [i2] {
return false
}
i1 = i1.successor()
i2 = i2.predecessor()
}
return true
}
func reversed(s:String) -> String {
return String(s.characters.reverse())
}
func add(s:String, _ u:String) -> String {
let long = s.utf8.count > u.utf8.count ? s.utf8 : u.utf8
let short = s.utf8.count > u.utf8.count ? u.utf8 : s.utf8
var flag:UInt8 = 0
var e:UInt8 = 0
var resultArray = [UInt8]()
for i in 0..<short.count {
let a = long[advance(long.startIndex, short.count - i - 1)] - 48
let b = short[advance(short.startIndex, short.count - i - 1)] - 48
e = a + b + flag
if e > 9 {
flag = 1
e = e % 10
} else {
flag = 0
}
resultArray.append(e)
}
for i in 0..<(long.count-short.count) {
let a = long[advance(long.endIndex, -1 - i)] - 48
e = a + flag
if e > 9 {
flag = 1
e = e % 10
} else {
flag = 0
}
resultArray.append(e)
}
if flag > 0 {
resultArray.append(flag)
}
return "".join(resultArray.map{ String($0) })
}
func test(var s:String) -> Bool {
for _ in 1..<50 {
let s1 = reversed(s)
s = add(s, s1)
if isPalindrome(s) {
return false
}
}
return true
}
timeit {
let r = Array(1...10000).filter{ test("\($0)") }.count
print(r)
}
//249
//time: 6828.21297645569 ms
Raw
e056.swift
#!/usr/bin/swift
func timeit(@noescape f: () -> ()) {
let begin = NSDate()
f()
let elapsed = NSDate().timeIntervalSinceDate(begin)
print("time: \(elapsed) ms")
}
struct BigInt: CustomStringConvertible {
// Swift 2.0 에서는 Printable이 CustomStringConvertible로 변경됨
static let UNIT = 100000000 // 8자리씩 끊어서 이용함. 32비트에서는 4자리로.
let unit_count = 8
typealias NumberBucket = (Int, Int)
let data: [NumberBucket]
init(_ buckets: [NumberBucket]) {
data = BigInt.roundUp(buckets)
}
init(var _ intValue:Int) {
var level = 0
var temp = [NumberBucket]()
while intValue > 0 {
temp.append((intValue % BigInt.UNIT, level))
level += 1
intValue = intValue / BigInt.UNIT
}
data = temp
}
init(_ strValue:String) {
var level = 0
var temp = [NumberBucket]()
let u = Array(strValue.utf8).map{ Int($0) - 48 }
let l = u.count
for a in 0...l/unit_count {
var d = 0
for b in 0..<unit_count {
let c = l - (unit_count * a + unit_count - b - 1) - 1
if c < 0 {
continue
}
d = d * 10 + u[c]
}
temp.append((d, level))
level += 1
}
data = temp
}
var description: String {
let d = data.sort{ $0.1 > $1.1 }
return "\(d[0].0)" + d[1..<d.count].map{String(format:"%04d", $0.0)}.joinWithSeparator("")
// return "".join(d.map{String($0)})
}
static func roundUp(buckets:[NumberBucket]) -> [NumberBucket] {
let maxKey = buckets.map{ $0.1 }.reduce(buckets[0].1){ $0 > $1 ? $0 : $1 }
var result = [NumberBucket]()
var flag = 0
for k in 0...maxKey {
var s = buckets.filter{ $0.1 == k }.map{ $0.0 }.reduce(flag, combine: +)
if s >= BigInt.UNIT {
flag = s / BigInt.UNIT
s = s % BigInt.UNIT
} else {
flag = 0
}
result.append((s, k))
}
if flag > 0 {
result.append((flag, maxKey+1))
}
return result
}
static func multiplyNumberBucket(l:NumberBucket, _ r:NumberBucket) -> [NumberBucket] {
let x = l.0 * r.0
let y = l.1 + r.1
if x < BigInt.UNIT {
return [(x, y)]
}
return [(x % BigInt.UNIT, y), (x / BigInt.UNIT, y+1)]
}
func add(target:BigInt) -> BigInt {
return BigInt(data + target.data)
}
func multiply(target:BigInt) -> BigInt {
var result = [NumberBucket]()
for a in data {
for b in target.data {
result += BigInt.multiplyNumberBucket(a, b)
}
}
return BigInt(result)
}
}
func +(lhs:BigInt, rhs:BigInt) -> BigInt {
return lhs.add(rhs)
}
func *(lhs:BigInt, rhs:BigInt) -> BigInt {
return lhs.multiply(rhs)
}
func powString(a: Int, _ b: Int) -> BigInt {
var x = BigInt(1)
let y = BigInt(a)
for _ in 1...b {
x = x * y
}
return x
}
func sumOfAllDigits(n: BigInt) -> Int {
return "\(n)".characters.map{ Int(String($0))! }.reduce(0, combine: +)
}
timeit {
var result = [BigInt]()
for i in 2...99 {
for j in 2...99 {
result.append(powString(i, j))
}
}
let maxValue = result.map(sumOfAllDigits)
.reduce(0){ $0 > $1 ? $0 : $1 }
print(maxValue)
// 972
// 12.83... ms (컴파일한 후 실행 시)
}
Raw
e058.swift
/*숫자를 1부터 시작해서 하나씩 늘려가며 아래와 같이 시계반대방향으로 감아가면 한 변의 크기가 7인 정사각형 소용돌이가 만들어집니다.
37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18 5 4 3 12 29
40 19 6 1 2 11 28
41 20 7 8 9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49
우하단 대각선쪽으로 홀수 제곱수(9, 25, 49)들이 늘어서 있는 것이 눈에 띕니다만, 더 흥미로운 사실은 양 대각선상에 놓인 13개의 숫자 중 8개가 소수라는 것입니다. 그 비율은 대략 8/13 ≈ 62% 정도가 됩니다.
이런 식으로 계속 소용돌이를 만들어갈 때, 양 대각선상의 소수 비율이 처음으로 10% 미만이 되는 것은 언제입니까? 정사각형 한 변의 크기로 답하세요.*/
/** 1부터 시작해서
2씩 커지면서 4번으로 한 바퀴를 돈다. (각 시행에서 나오는 값은 모서리값)
매번 각 모서리값의 개수와 소수인 모서리값의 개수 1씩 올리면서
한바퀴를 다 돌면 그 비율을 확인한다.
**/
//Swift 2.0
import Foundation
func timeit(@noescape f:()->()) {
let s = NSDate()
f()
let e = NSDate().timeIntervalSinceDate(s)
print("time: \(e*1000) ms")
}
func isPrime(n:Int) -> Bool {
switch true {
case n == 2, n == 3:
return true
case n < 2:
return false
case n % 2 == 0, n % 3 == 0:
return false
case n < 9:
return true
default:
let l = Int(floor(sqrt(Double(n))))
var k = 5
while k <= l {
if n % k == 0 || n % (k + 2) == 0 {
return false
}
k += 6
}
return true
}
}
timeit{
var a: [Int] = [1]
var k = 2
var n = 1
var ncount = 1
var pcount = 0
while true {
for _ in 1...4 {
n = n + k
if isPrime(n) {
pcount++
}
ncount++
}
if pcount * 10 < ncount {
print(k+1)
return
}
k += 2
}
}
//6241
//time: 394.385993480682 ms
Raw
e060.swift
#!/usr/bin/swift
/*
네 개의 소수 3, 7, 109, 673은 상당히 특이한 성질이 있습니다. 넷 중에 아무것이나 두 개를 골라서 어떤 쪽으로 이어붙이던지 그 결과도 소수가 됩니다. 예를 들어 7과 109를 고르면 7109와 1097 또한 소수입니다.
3, 7, 109, 673는 이런 성질을 가진 네 소수 중에서 그 합이 792로 가장 작습니다,
다섯 소수 중에 어떤 두 개를 골라 이어붙여도 소수가 되는 수들을 찾아서, 그 합의 최소값을 구하세요.*/
import Foundation
func timeit(@noescape f:() -> Void) {
let s = NSDate()
f()
let e = NSDate().timeIntervalSinceDate(s)
print("time: \(e * 1000) ms")
}
func _isPrime(n: Int) -> Bool {
switch true {
case n < 2:
return false
case n == 2, n == 3, n == 5, n == 7:
return true
case n % 2 == 0, n % 3 == 0:
return false
default:
let l = Int(floor(sqrt(Double(n))))
var k = 5
while !(k > l) {
if n % k == 0 {
return false
}
if n % (k + 2) == 0 {
return false
}
k += 6
}
return true
}
}
func memoize<T: Hashable, U> (f:(T) -> U) -> T -> U
{
var cache = [T:U]()
let result: T -> U = { x in
if let r = cache[x] {
return r
}
let r = f(x)
cache[x] = r
return r
}
return result
}
let isPrime = memoize(_isPrime)
let primes = Array(3...9999).filter(isPrime)
func test(a: Int, _ b: Int) -> Bool {
guard a != b else { return false }
guard let x = Int("\(a)\(b)") where isPrime(x) else { return false }
guard let y = Int("\(b)\(a)") where isPrime(y) else { return false }
return true
}
let hence = 4
func process(xs:[Int], _ depth: Int = 1) -> [Int] {
// 5개 세트까지 다 찾은 경우
if depth > hence {
return xs
}
for x in xs {
// i개 끼리 붙여서 소수가 되는 집합에서 x를 꺼내어....
let ys = xs.filter{ test($0, x) }
if ys.count < hence - depth {
continue
}
var result = process(ys, depth+1)
if !result.isEmpty {
result.append(x)
return result
}
}
return []
}
timeit{
let r = process(primes)
print(r)
print(r.reduce(0, combine: +))
// [8389, 6733, 5701, 5197, 13]
// 26033
// time: 525.063991546631 ms
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment