/**
* Check whether a number is prime.
* Uses a √n loop and skips even numbers after 2.
*/
function isPrime(value: number): boolean {
if (value < 2) return false;
if (value === 2) return true;
if (value % 2 === 0) return false;
const limit: number = Math.floor(Math.sqrt(value));
for (let d: number = 3; d <= limit; d += 2) {
if (value % d === 0) return false;
}
return true;
}
/**
* Generate all primes up to N.
* Any consecutive prime sum equal to N cannot contain primes larger than N.
*/
function generatePrimes(maxN: number): number[] {
const primes: number[] = [];
for (let n: number = 2; n <= maxN; n++) {
if (isPrime(n)) primes.push(n);
}
return primes;
}
/**
* 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
*/
function findPrimeConsecutiveSums(N: number): void {
const primes: number[] = generatePrimes(N);
let start: number = 0;
let end: number = 0;
let sum: number = 0;
while (true) {
if (sum < N) {
if (end === primes.length) break;
sum += primes[end++];
} else if (sum > N) {
sum -= primes[start++];
} else {
// Found a valid sequence
console.log("Sequence:", primes.slice(start, end).join(" "));
// Continue searching
sum -= primes[start++];
}
}
}
/**
* main
*/
const N: number = 41;
console.log(`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
*/
