Count Composite Numbers in an Array

Title: Count Composite Numbers in an Array

In this guide, you will learn how to count the composite numbers in an array using Java. A composite is an integer greater than 1 that is not prime, and the problem is a tidy inversion of the “count primes” method with one important twist in the definition.

We will walk through the problem, build a complete program with an O(sqrt(n)) helper, trace it on a sample input, and then look at the “composite is not just non-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 composite. A composite integer is strictly greater than 1 and has at least one divisor other than 1 and itself. The smallest composite is 4, and 9 is the smallest odd composite.

The subtle part is that composite is not simply “not prime”. By convention, 0, 1, and every negative integer are neither prime nor composite. A naive !isPrime(n) implementation would wrongly count all three groups, so the helper has to reject anything below 4 up front.

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 isComposite(value) on each element, incrementing count when the helper returns true.
4. Inside isComposite, return false immediately for any value less than 4. This single guard covers negatives, 0, 1, 2, and 3 in one check, which handles the “neither prime nor composite” group and the two smallest primes together.
5. Return true for any even value from 4 onward, since the only even prime is 2 and it is already handled by the earlier guard.
6. Test odd divisors from 3 up to sqrt(n) inclusive. The first hit means n is composite; surviving the loop with no hit means n is prime, so return false.
7. 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 CountComposites {
    public static int countComposites(int[] numbers) {
        if (numbers == null) {
            throw new IllegalArgumentException("Array must not be null");
        }
        int count = 0;
        for (int value : numbers) {
            if (isComposite(value)) {
                count++;
            }
        }
        return count;
    }

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

    public static void main(String[] args) {
        int[] values = {2, 4, 7, 9, 10, 11, 15};
        int composites = countComposites(values);
        System.out.println("Composite count: " + composites);
    }
}

Explanation of the Program

The class CountComposites exposes a public countComposites method for the outer loop and a private isComposite helper for the per-element test. Separating the two concerns makes the main loop a two-line read and keeps the compositeness 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 composite. The empty array is accepted and returns 0, which is the honest count for a dataset of size zero.

Inside isComposite, the first guard n < 4 rejects everything below the smallest composite. That single check covers five groups: all negatives, 0, 1, 2, and 3. Grouping them together is cleaner than four separate guards, and it reflects the mathematical convention that only integers greater than 1 can be composite.

The next check, n % 2 == 0, returns true immediately. Any even value of 4 or greater is divisible by 2 on top of 1 and itself, so it is composite by definition. Having the even case handled up front lets the main loop skip even divisors.

The main loop tests only odd divisors starting at 3 and incrementing by 2. Any composite n has at least one factor at most sqrt(n), so the loop stops once i * i exceeds n. Finding any divisor returns true; exhausting the loop without a hit returns false. Compared with the symmetric isPrime helper, both return paths are flipped.

The subtle part of the loop is the 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 and keeps the comparison honest.

The main method is a tiny driver: it builds a mix of primes, composites, and the boundary values 2 and 7, calls countComposites, and prints the result. Running it prints Composite count: 4, which matches the composites 4, 9, 10, and 15 in the input.

Step-by-Step Trace

Let us trace countComposites on the input [1, 4, 6, 7, 9, 2]. The expected final answer is 3, since the composites are 4, 6, and 9.

At the end of iteration i, count holds the number of composites among numbers[0..i-1]. The trace exercises every branch of the helper: the small-value guard (1, 2), the even-divisibility fast path (4, 6), the odd-divisor hit (9), and the odd-divisor loop exiting without a factor (7, which is prime).

Examples

Example 1: Mixed primes and composites

A short block of consecutive integers so both isComposite branches are exercised.

int[] nums = {4, 5, 6, 7, 8, 9};
int composites = countComposites(nums);
System.out.println(composites);
// Composites: 4, 6, 8, 9
// Output: 4

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

Nothing in this input is composite: negatives, 0, and 1 are rejected by the first guard, and the two primes 2 and 3 are rejected by the same guard because they are below 4.

int[] nums = {-5, 0, 1, 2, 3, 5};
int composites = countComposites(nums);
System.out.println(composites);
// Output: 0

Example 3: All composites

Every value is composite, so the count equals the array length. The odd composites 9 and 15 are caught by the odd-divisor loop; the even ones go through the fast path.

int[] nums = {4, 6, 8, 9, 10, 15};
int composites = countComposites(nums);
System.out.println(composites);
// Output: 6

Common Mistakes to Avoid

The algorithm is short, but the definition of “composite” and the inverted return paths together produce several reliable traps. These are the mistakes learners actually make on this problem.

• Returning !isPrime(n) – looks right, but isPrime returns false for 0, 1, and every negative, so the negation counts all of those as composite. That silently inflates the result on any array with non-positive values. Keep a dedicated isComposite helper with its own n < 4 guard.
• Treating 1 as composite – by mathematical convention, 1 is neither prime nor composite, so a method that counts it is wrong. The n < 4 guard covers this case for free.
• Treating 0 or negatives as composite – compositeness is defined only for integers greater than 1. Letting any non-positive slip through makes every downstream statistic wrong.
• 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 effectively forever depending on which side of zero the wrap lands on. Use (long) i * i.
• Returning false on the first odd value – placing the false return inside the if body instead of after the loop exits the method as soon as any odd non-divisor is encountered, so odd primes come back as true and get counted as composite. The return false; belongs after the loop.

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 0 and 1 (neither is composite)
• Array of only small primes [2, 3, 5, 7] (none composite)
• Array containing 4 (the smallest composite)
• Array containing 9, 25, 49 (smallest odd composites, hit by the odd-divisor loop)
• Integer.MAX_VALUE present (prime M31, not composite)
• Integer.MAX_VALUE - 2 present (composite: 5 * 429496729)

Additional Considerations

The per-element compositeness 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 with true at index i meaning “i is composite”, then each query becomes an O(1) array lookup. Remember that the sieve indices 0, 1, and every negative query still need the “neither prime nor composite” guard, since the sieve itself does not represent that distinction.

The pair Integer.MAX_VALUE and Integer.MAX_VALUE - 2 on the edge-case list is a useful final sanity check. The value 2147483647 is the Mersenne prime 2^31 - 1, so a correct implementation must count it as not composite; the value 2147483645 is 5 * 429496729, so it must be counted as composite. A loop that overflows i * i typically breaks the second case silently.

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 composites up to N rather than inside a specific array? – run a Sieve of Eratosthenes in O(N log log N), then count every index i in 4..N whose sieve entry is marked composite.
• How would you speed up counting composites in a very long array when the maximum value is small? – precompute a sieve up to the maximum, then replace the per-element isComposite call with a single lookup. The method becomes O(N log log N + m).
• How would you count semiprimes (composites that are the product of exactly two primes) inside the array? – factorise each candidate up to sqrt(n), keep only the ones with exactly two prime factors counted with multiplicity (so 4 = 2 * 2 and 15 = 3 * 5 both qualify).
• How would you count composites with exactly k prime factors (counted with multiplicity)? – the same factorisation extended to track the big-omega count; a sieve of smallest prime factors makes the per-element work closer to O(log n).
• How would you count composites in a very large array in parallel? – use Arrays.stream(numbers).parallel().filter(CountComposites::isComposite).count(), which splits the array into chunks, counts each chunk independently, and sums the chunk counts.

Conclusion

Counting the composite numbers in an array in Java is an outer one-pass loop built around an O(sqrt(n)) helper, with three decisions tucked inside the helper: reject every value below 4 up front (because negatives, 0, 1, 2, and 3 are not composite), return true for every even value from 4 onward, 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, semiprime counting, 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, keeping the n < 4 guard in place so 0, 1, and negatives are still excluded. 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.