/**
* Checks whether a number is prime.
* Uses a √n loop and skips even numbers after 2.
*/
fun isPrime(value: Int): Boolean {
if (value < 2) return false
if (value == 2) return true
if (value % 2 == 0) return false
val limit = kotlin.math.sqrt(value.toDouble()).toInt()
var d = 3
while (d <= limit) {
if (value % d == 0) return false
d += 2
}
return true
}
/**
* Generates all primes up to N.
* Any consecutive prime sum equal to N cannot contain primes larger than N.
*/
fun generatePrimes(maxN: Int): List<Int> =
(2..maxN).filter { isPrime(it) }
/**
* Finds 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
*/
fun findPrimeConsecutiveSums(N: Int) {
val primes = generatePrimes(N)
var start = 0
var end = 0
var sum = 0
while (true) {
when {
sum < N -> {
if (end == primes.size) return
sum += primes[end]
end++
}
sum > N -> {
sum -= primes[start]
start++
}
else -> {
// Found a valid sequence
println("Sequence: ${primes.subList(start, end).joinToString(" ")}")
// Continue searching
sum -= primes[start]
start++
}
}
}
}
/**
* main
*/
fun main() {
val N = 41
println("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
*/
