에라토스테네스의 체를 통해 주어진 수보다 작은 소수 배열을 구한다. 해당 소수 배열의 누적합을 구하고, 누적합을 통해 특정 구간의 합을 얻어낼 수 있다. 해당 구간의 합이 주어진 수와 같다면 곧바로 브레이크하면서 카운팅한다.
import Foundation
let N = Int(String(readLine()!))!
let primes = eratos(N)
var accumulatedPrimes = getAccumulatedPrimes(primes)
var total = 0
for idx1 in 0..<accumulatedPrimes.count {
let first = accumulatedPrimes[idx1]
for idx2 in idx1..<accumulatedPrimes.count {
let second = accumulatedPrimes[idx2]
if second - first == N {
total += 1
break
} else if second - first > N {
break
}
}
}
print(total)
func getAccumulatedPrimes(_ primes: [Int]) -> [Int] {
if primes.isEmpty {
return []
}
var tmp = [Int]()
tmp.append(primes[0])
for idx in 1..<primes.count {
guard let last = tmp.last else { break }
let newValue = last + primes[idx]
tmp.append(newValue)
}
return [0] + tmp
}
func eratos(_ number: Int) -> [Int] {
var numbers = Array(repeating: true, count: number + 1)
numbers[0] = false
numbers[1] = false
for idx in 2..<numbers.count {
if numbers[idx] {
if idx * 2 < numbers.count {
for idx2 in stride(from: idx * 2, to: numbers.count, by: idx) {
numbers[idx2] = false
}
}
}
}
let filteredNumbers = numbers.enumerated().filter{$0.element}.map{$0.offset}
return filteredNumbers
}