/**
* Check whether a number is prime.
* Uses a √n loop and skips even numbers after 2.
*/
def isPrime(value: Int): Boolean = {
if (value < 2) return false
if (value == 2) return true
if (value % 2 == 0) return false
val limit = math.sqrt(value.toDouble).toInt
var d = 3
while (d <= limit) {
if (value % d == 0) return false
d += 2
}
true
}
/**
* Generate all primes up to N.
* Any consecutive prime sum equal to N cannot contain primes larger than N.
*/
def generatePrimes(maxN: Int): Vector[Int] =
(2 to maxN).filter(isPrime).toVector
/**
* 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
*/
def findPrimeConsecutiveSums(N: Int): Unit = {
val primes = generatePrimes(N)
var start = 0
var end = 0
var sum = 0
while (true) {
if (sum < N) {
if (end == primes.length) return
sum += primes(end)
end += 1
} else if (sum > N) {
sum -= primes(start)
start += 1
} else {
// Found a valid sequence
println(s"Sequence: ${primes.slice(start, end).mkString(" ")}")
// Continue searching
sum -= primes(start)
start += 1
}
}
}
/**
* main
*/
@main def run(): Unit = {
val N = 41
println(s"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
*/
