Skip to content

Instantly share code, notes, and snippets.

@sooop

sooop/e050.swift Secret

Created Aug 23, 2017
Embed
What would you like to do?
// 준비작업 - 소수체를 생성하고, 누적합 리스트를 만든다.
let limit = 100_0000
let seive: [Bool] = {
var s = [false, false] + Array(repeating: true, count:limit)
for i in 2...limit where s[i] {
for j in stride(from:i*2, through:limit, by:i) { s[j] = false }
}
return s
}()
let isPrime: (Int) -> Bool = { seive[$0] }
let primes: [Int] = (1...limit).filter(isPrime)
var sums: [Int] = {
var xs = Array(repeating: 0, count: 1 + primes.count)
for i in 1..<xs.count {
xs[i] = xs[i-1] + primes[i-1]
}
return xs.filter{ $0 < limit * 2 }
}()
// 최대길이를 줄여나가고, 오프셋값을 늘려나가며 조건에 맞는 부분합을 찾는다.
main: do {
let maxLength = sums.count - 1
for l in stride(from: maxLength, to:0, by: -1) {
for offset in 0..<(maxLength - l) {
let gap = sums[l+offset+1] - sums[offset]
if gap <= limit {
if isPrime(gap){
print(gap)
break main
}
} else {
break
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment