import Foundation
/*
Check whether a number is prime.
Uses a √n loop and skips even numbers after 2.
*/
func isPrime(_ value: Int) -> Bool {
if value < 2 { return false }
if value == 2 { return true }
if value % 2 == 0 { return false }
let limit = Int(Double(value).squareRoot())
var d = 3
while d <= limit {
if value % d == 0 { return false }
d += 2
}
return true
}
/*
Generate all primes up to N.
Any consecutive prime sum equal to N cannot contain primes larger than N.
*/
func generatePrimes(upTo maxN: Int) -> [Int] {
(2...maxN).filter { isPrime($0) }
}
/*
Find all consecutive prime sequences whose sum equals N.
Uses a sliding window:
- Expand the window by moving the right pointer
- Shrink the window by moving the left pointer
*/
func findPrimeConsecutiveSums(_ N: Int) {
let primes = generatePrimes(upTo: N)
var start = 0
var end = 0
var sum = 0
while true {
if sum < N {
if end == primes.count { break }
sum += primes[end]
end += 1
} else if sum > N {
sum -= primes[start]
start += 1
} else {
// Found a valid sequence
print("Sequence:", primes[start..<end].map(String.init).joined(separator: " "))
// Continue searching
sum -= primes[start]
start += 1
}
}
}
/*
main
*/
let N = 41
print("Consecutive prime sequences whose sum equals \(N):")
findPrimeConsecutiveSums(N)
/*
run:
Consecutive prime sequences whose sum equals 41:
Sequence: 2 3 5 7 11 13
Sequence: 11 13 17
Sequence: 41
*/
