Count Prime Numbers in an Array

Title: Count Prime Numbers in an Array

In this guide, you will learn how to count the prime numbers in an array using Java. The problem is the first array exercise where the per-element check is non-trivial, and it is a surprisingly good lens into trial-division optimisations, two’s-complement overflow, and the Sieve of Eratosthenes.

We will walk through the problem, build a complete program with an O(sqrt(n)) primality test, trace it on a sample input, and then look at the “is 1 prime?” trap, the i * i overflow fix, and the follow-up questions a Java interviewer tends to ask on this problem.

Understanding the Problem

Given an array of n integers, the task is to return how many of them are prime. A prime is an integer strictly greater than 1 whose only positive divisors are 1 and itself. The smallest prime is 2, and 2 is also the only even prime; every other even integer is divisible by 2 on top of 1 and itself.

For the input [2, 4, 7, 10, 11, 13, 15], the primes are 2, 7, 11, and 13, so the answer is 4. Values less than 2, including 0, 1, and every negative, are not prime by definition.

Approach / Algorithm Steps

1. Reject the input early if the array is null. An empty array is fine: its count is 0.
2. Declare a counter count initialised to 0.
3. Walk the array and call a helper isPrime(value) on each element, incrementing count when the helper returns true.
4. Inside isPrime, return false immediately for any value less than or equal to 1. Handle 2 as a special true case so the main loop can skip even divisors afterwards.
5. Return false for any even value greater than 2, then test odd divisors from 3 up to sqrt(n) inclusive. The square-root bound is enough because any composite n has at least one factor at most sqrt(n).
6. Widen i * i to long before comparing against n. A plain int multiplication overflows for i near 46341, which is reachable when n is close to Integer.MAX_VALUE.

Java Program

public class CountPrimes {
    public static int countPrimes(int[] numbers) {
        if (numbers == null) {
            throw new IllegalArgumentException("Array must not be null");
        }
        int count = 0;
        for (int value : numbers) {
            if (isPrime(value)) {
                count++;
            }
        }
        return count;
    }

    private static boolean isPrime(int n) {
        if (n <= 1) {
            return false;
        }
        if (n == 2) {
            return true;
        }
        if (n % 2 == 0) {
            return false;
        }
        for (int i = 3; (long) i * i <= n; i += 2) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[] values = {2, 4, 7, 10, 11, 13, 15};
        int primes = countPrimes(values);
        System.out.println("Prime count: " + primes);
    }
}

Explanation of the Program

The class CountPrimes exposes a public countPrimes method for the outer loop and a private isPrime helper for the per-element test. Separating the two concerns makes the main loop a two-line read and keeps the primality rules in one place.

The outer method validates against null, iterates with an enhanced for loop, and increments the counter when the helper says the current value is prime. The empty array is accepted and returns 0, which is the honest count for a dataset of size zero.

Inside isPrime, three guard clauses handle the small cases. Any n <= 1 is non-prime by definition, including 0, 1, and every negative. The number 2 is the only even prime, so it is returned as true up front; after that, every even value is composite and can be rejected with a single modulo check.

The main loop tests only odd divisors starting at 3, incrementing by 2 each time. Any composite n has at least one factor at most sqrt(n), so the loop stops once i * i exceeds n. That turns the per-element work from O(n) trial division into O(sqrt(n)).

The subtle part of that loop is the loop condition (long) i * i <= n. For n near Integer.MAX_VALUE, the loop variable i climbs past 46340, and 46341 * 46341 in plain int arithmetic overflows to a negative value. The (long) cast on i promotes the multiplication to long, which has enough headroom for the squared value and keeps the comparison honest.

The main method is a tiny driver: it builds a mix of primes and composites, calls countPrimes, and prints the result. Running it prints Prime count: 4, which matches the primes 2, 7, 11, and 13 in the input.

Step-by-Step Trace

Let us trace countPrimes on the input [6, 2, 9, 11, 4, 13]. The expected final answer is 3, since the primes are 2, 11, and 13.

At the end of iteration i, count holds the number of primes among numbers[0..i-1]. The trace shows every isPrime branch at least once: the small-case shortcut (2), the even-divisibility fast path (4, 6), the odd-divisor hit (9), and the odd-divisor loop exiting without a factor (11, 13).

Examples

Example 1: Mixed primes and composites

A classic input covering the first several integers so every branch of the helper is exercised.

int[] nums = {2, 3, 4, 5, 6, 7, 8, 9, 10};
int primes = countPrimes(nums);
System.out.println(primes);
// Primes: 2, 3, 5, 7
// Output: 4

Example 2: Non-positive values, 1, and small primes

Values at or below 1 are not prime, so negatives, 0, and 1 are all excluded by the first guard clause.

int[] nums = {-7, 0, 1, 2, 3};
int primes = countPrimes(nums);
System.out.println(primes);
// Primes: 2, 3
// Output: 2

Example 3: All composites

No element passes the primality test, so the count stays at 0. The composites include an odd perfect square, 9, which is caught by the first odd divisor 3.

int[] nums = {4, 6, 8, 9, 10};
int primes = countPrimes(nums);
System.out.println(primes);
// Output: 0

Common Mistakes to Avoid

The primality test is the smallest piece of real algorithmic code most learners write, and it concentrates a lot of mistakes into a few lines. These are the ones you actually see.

• Treating 1 as prime – modern mathematics defines a prime as an integer strictly greater than 1, so 1 is excluded. Letting it slip through makes every downstream count, factorisation, and sieve subtly wrong. Reject n <= 1 up front.
• Treating 2 as non-prime – jumping straight from “skip evens” to the odd-divisor loop drops 2 itself, since it is both even and the only even prime. Handle 2 as a special true case before the even-divisibility check.
• i * i overflow – for n close to Integer.MAX_VALUE, the loop variable grows past 46340 and 46341 * 46341 wraps to a negative int. The loop then exits early or runs forever depending on which side of zero the wrap lands on. Use (long) i * i.
• Checking divisors all the way to n – running the inner loop up to n - 1 turns an O(sqrt(n)) test into an O(n) one, and the full array scan into O(n * m) where m is the largest value. Stop at sqrt(n) inclusive.
• Ignoring negatives and 0 – the odd-divisor loop would never execute for a negative n, so the method returns true and counts every negative as prime. The n <= 1 guard handles negatives, 0, and 1 in one check.

Edge Cases to Test

Walk through this checklist before you call the solution done. The first few are the ones an interviewer is most likely to probe.

• Empty array (count is 0)
• Null array reference
• Array containing only 1 (not prime)
• Array containing only 2 (prime; the smallest and only even prime)
• Array containing 0, 1, and negatives (none prime)
• Odd perfect squares such as 9, 25, 49 (composite, caught by the first few odd divisors)
• Large primes near Integer.MAX_VALUE (the overflow test)
• Integer.MAX_VALUE itself is prime (2^31 - 1 is the Mersenne prime M31)

Additional Considerations

The per-element primality test runs in O(sqrt(n)) time with O(1) extra space. For an array of length m whose largest value is n, the whole method is bounded by O(m * sqrt(n)), which is already fast enough for arrays of a few thousand values with entries up to Integer.MAX_VALUE.

If the array contains many values and the maximum value N is bounded, the Sieve of Eratosthenes is the right tool. Build a boolean[N + 1] once in O(N log log N) time, then each query becomes an O(1) array lookup. The sieve pays for itself the moment the array is longer than roughly sqrt(N).

The Integer.MAX_VALUE entry on the edge-case list is a useful final sanity check. The value 2147483647 happens to be the Mersenne prime 2^31 - 1, so a correct implementation must count it as prime; a loop that overflows i * i typically either exits too early (counts it anyway) or runs effectively forever, both of which fail silently without the (long) cast.

Interview Follow-up Questions

The base problem is only the opening move. A real interviewer will push with questions like these, each probing a different axis of the solution.

• How would you count primes up to N rather than inside a specific array? – build a boolean[N + 1] sieve of Eratosthenes in O(N log log N), then count the true entries at indices 2..N.
• How would you speed up counting primes in a very long array when the maximum value is small? – precompute a sieve up to the maximum, then replace the per-element isPrime call with a single lookup. The method becomes O(N log log N + m).
• How would you test primality for 64-bit values that do not fit in int? – trial division to sqrt(n) still works, but Miller-Rabin with a fixed base set gives a deterministic answer for all 64-bit integers in a few modular exponentiations.
• How would you count primes in a very large array in parallel? – use Arrays.stream(numbers).parallel().filter(CountPrimes::isPrime).count(), which splits the array into chunks, counts each chunk independently, and sums the chunk counts.
• How would you count twin primes (pairs p, p + 2 that are both prime) inside an array? – combine the primality test with a scan over consecutive values after sorting, or precompute primality for every candidate first and then count the pairs in one pass.

Conclusion

Counting the prime numbers in an array in Java is an outer one-pass loop built around an O(sqrt(n)) primality helper, with three decisions tucked inside the helper: reject every value at or below 1 up front, treat 2 as a special case so the main loop can skip even divisors, and widen i * i to long so the loop condition stays correct for n near Integer.MAX_VALUE. Once those three habits are in place, the same shape of code extends cleanly to sieves, Miller-Rabin, and parallel reduce at scale.

Try adapting the code above to replace the per-element helper with a precomputed Sieve of Eratosthenes bounded by the array’s maximum value, and benchmark the two versions on inputs of a few million random values. The sieve wins once the array is longer than roughly the square root of the maximum.

You can learn more Array problems like this one here: Arrays.