import java.util.ArrayList;
import java.util.List;
/**
* Check whether a number is prime.
* Uses a √n loop and skips even numbers after 2.
*/
public class PrimeConsecutiveSum {
static boolean isPrime(int value) {
if (value < 2) return false;
if (value == 2) return true;
if (value % 2 == 0) return false;
int limit = (int) Math.sqrt(value);
for (int d = 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.
*/
static List<Integer> generatePrimes(int maxN) {
List<Integer> primes = new ArrayList<>();
for (int n = 2; n <= maxN; n++) {
if (isPrime(n)) {
primes.add(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
*/
static void findPrimeConsecutiveSums(int N) {
List<Integer> primes = generatePrimes(N);
int start = 0;
int end = 0;
int sum = 0;
while (true) {
if (sum < N) {
if (end == primes.size()) break;
sum += primes.get(end++);
} else if (sum > N) {
sum -= primes.get(start++);
} else {
// Found a valid sequence
System.out.print("Sequence: ");
for (int i = start; i < end; i++) {
System.out.print(primes.get(i) + " ");
}
System.out.println();
// Continue searching
sum -= primes.get(start++);
}
}
}
/**
* main
*/
public static void main(String[] args) {
int N = 41;
System.out.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
*/