import math
# ------------------------------------------------------------
# Check whether a number is prime.
# Uses a √n loop and skips even numbers after 2.
# ------------------------------------------------------------
def is_prime(value: int) -> bool:
if value < 2:
return False
if value == 2:
return True
if value % 2 == 0:
return False
limit = int(math.sqrt(value))
for d in range(3, limit + 1, 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, so this upper bound is sufficient.
# ------------------------------------------------------------
def generate_primes(max_n: int) -> list[int]:
return [n for n in range(2, max_n + 1) if is_prime(n)]
# ------------------------------------------------------------
# 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 find_prime_consecutive_sums(N: int) -> None:
primes = generate_primes(N)
start = 0
end = 0
current_sum = 0
while True:
if current_sum < N:
if end == len(primes):
break
current_sum += primes[end]
end += 1
elif current_sum > N:
current_sum -= primes[start]
start += 1
else:
# Found a valid sequence
print("Sequence:", *primes[start:end])
# Continue searching
current_sum -= primes[start]
start += 1
# ------------------------------------------------------------
# main
# ------------------------------------------------------------
if __name__ == "__main__":
N = 41
print(f"Consecutive prime sequences whose sum equals {N}:")
find_prime_consecutive_sums(N)
"""
run:
Consecutive prime sequences whose sum equals 41:
Sequence: 2 3 5 7 11 13
Sequence: 11 13 17
Sequence: 41
"""