Sum of Prime Elements in an Array

Title: Sum of Prime Elements in an Array

Prime numbers sit at the heart of many classic Java interview questions, and summing the primes inside an array is one of the cleanest ways to practice the pattern. In this guide, you’ll learn how to build a small, well structured Java program that scans an integer array, decides whether each element is prime, and accumulates a running total.

We’ll walk through the problem definition, the algorithm, the full Java program, a dry run on real values, worked examples, common mistakes, edge cases, complexity, and a few interview follow-up questions. By the end, you’ll have a reusable mental template for any “scan an array and sum the elements that satisfy a predicate” problem.

Understanding the Problem

Given an integer array numbers, we want to compute the sum of every element that is a prime number. A prime number is an integer greater than 1 whose only positive divisors are 1 and itself. So 2, 3, 5, 7, 11, 13 are prime, while 0, 1, 4, 6, and every negative integer are not.

For an input like {2, 4, 5, 6, 7, 9, 11}, the primes are 2, 5, 7, and 11, so the expected output is 25. Non prime values, zeros, and negatives contribute nothing to the sum.

Approach / Algorithm Steps

The algorithm has two tiny responsibilities: tell whether a single number is prime, and walk the array accumulating the primes. Keeping them separate makes both pieces easy to read and test.

1. Initialize an integer accumulator sum to 0.
2. Iterate over every element value in the input array.
3. For each value, call a helper method isPrime(value).
4. Inside isPrime, return false immediately when the number is less than 2.
5. Otherwise, test divisors i from 2 up to sqrt(number) using the condition i * i <= number.
6. If any divisor evenly divides number, return false; after the loop, return true.
7. Back in the caller, add value to sum only when isPrime returned true.
8. After the full scan, return sum as the final answer.

Java Program

public class SumOfPrimeElements {

    // Method: check if a number is prime
    public static boolean isPrime(int number) {
        if (number < 2) {
            return false;
        }
        for (int i = 2; i * i <= number; i++) {
            if (number % i == 0) {
                return false;
            }
        }
        return true;
    }

    // Method: sum all prime elements in the array
    public static int sumOfPrimes(int[] array) {
        int sum = 0;
        for (int value : array) {
            if (isPrime(value)) {
                sum += value;
            }
        }
        return sum;
    }

    // Main method: test the sumOfPrimes method
    public static void main(String[] args) {
        int[] numbers = {2, 4, 5, 6, 7, 9, 11};
        int result = sumOfPrimes(numbers);
        System.out.println("Sum of prime elements: " + result);
    }
}

Explanation of the Program

The class SumOfPrimeElements contains three methods. The helper isPrime takes a single int and returns a boolean. The guard if (number < 2) rules out 0, 1, and every negative number in one shot, because none of them are prime by definition.

The trial division loop runs i from 2 while i * i <= number. We stop at the square root of number because any composite factor larger than the square root must be paired with a smaller factor we already tested. The check number % i == 0 looks for a nontrivial divisor; finding one proves the number is composite and returns false immediately.

The second method sumOfPrimes keeps a running accumulator sum and iterates with an enhanced for loop. For every value that passes isPrime, we add it to sum. The main method sets up a sample array, calls the method, and prints the result through System.out.println.

Step-by-Step Trace

Trace the algorithm on the fresh input {3, 8, 13, 14, 17}. The target output is 33, because the prime elements are 3, 13, and 17.

At the end of iteration i, sum holds the total of every prime found in numbers[0..i-1]. The invariant holds whether the current element is prime or not, which is what makes the loop body safe to read line by line.

Examples

Example 1: Mixed Primes and Composites

The array holds a mix of primes and composite values. The primes 2, 3, 5, and 23 contribute, while 4, 10, and 15 are skipped.

int[] numbers = {2, 3, 4, 5, 10, 15, 23};
int result = sumOfPrimes(numbers);
System.out.println("Sum of prime elements: " + result);
// Output: Sum of prime elements: 33

Example 2: No Primes Present

When the array has no prime values, the accumulator never updates and the method returns 0. This is the baseline every correct implementation must pass before anything fancier.

int[] numbers = {1, 4, 6, 8, 9, 10};
int result = sumOfPrimes(numbers);
System.out.println("Sum of prime elements: " + result);
// Output: Sum of prime elements: 0

Example 3: Negatives and Zero

Negative integers and 0 are not prime, so they contribute nothing to the sum. Only 2 and 29 make it into the total.

int[] numbers = {-2, 0, 1, 2, 29};
int result = sumOfPrimes(numbers);
System.out.println("Sum of prime elements: " + result);
// Output: Sum of prime elements: 31

Common Mistakes to Avoid

A short checklist of mistakes that trip up most beginners on this problem.

• Treating 1 as prime – returns an inflated sum whenever the array contains 1, because the loop body never finds a divisor for it. Guard with if (number < 2) return false; before entering the trial division loop.
• Counting negatives as primes – inputs like -2 or -7 wrongly contribute negative values, which can even push the sum below zero. The same number < 2 guard rejects every negative integer in one branch.
• Looping up to number instead of sqrt(number) – correct but slow, turning each check into O(n) and the whole scan into O(n * m). Switch to for (int i = 2; i * i <= number; i++) for an O(sqrt(n)) primality test.
• Using Math.sqrt in the loop condition – introduces a double conversion and a method call per iteration, which quietly dominates runtime for large arrays. Prefer the integer check i * i <= number.
• Accumulating into an int when sums can overflow – silently wraps around when the running total exceeds Integer.MAX_VALUE, producing a negative output. Promote sum to long when inputs can be large or arrays are long.

Edge Cases to Test

Walk through these boundary inputs before you call the implementation done.

• Empty array
• Single-element array holding a prime
• Single-element array holding 1 or 0
• All composite elements
• All prime elements
• Array containing negative values
• Large primes near Integer.MAX_VALUE
• Null array reference

Additional Considerations

The outer loop runs n times, where n is the array length. Inside, isPrime costs O(sqrt(m)) where m is the current element. The overall time complexity is O(n * sqrt(m)), with m bounded by the largest value in the array. Space complexity is O(1) because we only keep a single integer accumulator and a few loop variables.

If you expect many large values, consider precomputing a Sieve of Eratosthenes up to the maximum element. The sieve costs O(m log log m) to build but turns every primality check into an O(1) array lookup, which is a big win when the same array is scanned many times or when the values are small and dense.

Watch for overflow when inputs are large. A long array of values near Integer.MAX_VALUE can push the running sum past the int ceiling and wrap around silently. Switching sum to long is a cheap defensive move; returning long from sumOfPrimes makes the contract explicit.

Interview Follow-up Questions

These are the natural extensions an interviewer will reach for once the base solution works.

• What if duplicates should only count once? – track visited primes in a HashSet<Integer> and only add a value when the set did not already contain it.
• What if the array elements can reach 10^7 and the array has millions of entries? – build a Sieve of Eratosthenes up to the maximum value once, then reduce each primality test to an O(1) boolean lookup.
• What if values can be as large as 10^12? – trial division by every integer up to the square root is too slow, so switch to a deterministic Miller-Rabin test with a known witness set for 64-bit integers.
• What if the array is streamed and does not fit in memory? – maintain a single running long accumulator, read one element at a time, and apply the same prime check; termination comes from end-of-stream.
• What if the input is distributed across many machines? – compute a partial prime sum per shard in parallel, then add the partial sums; the operation is associative, so the merge step is a simple reduction.

Conclusion

Summing the prime elements of an array is a compact exercise that blends two ideas you will reuse everywhere: a reusable predicate (isPrime) and an accumulate-while-you-filter loop. Keep the primality check honest about its guards, keep the loop bound at the square root, and the solution stays fast and readable.

Try adapting this program to related variants: sum of composite elements, product of primes, or counting primes within a sliding window. Each one swaps out one small piece of the template you just built.

You can learn more about Arrays: https://dailyjavaconcept.com/category/arrays/.