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

1 Answer

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

*/

 



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

Related questions

...