How to find all sequences of consecutive prime numbers whose sum equals N in Python

1 Answer

0 votes
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

"""

 



answered Jan 28, 2024 by avibootz
edited Aug 19 by avibootz

Related questions

...