Remove Primes using ArrayList

Input:

3 12 13 15

Output:

[12,15]

import java.util.ArrayList;
import java.util.Arrays;

public class RemovePrimes {
    public static void main(String[] args) {
        ArrayList<Integer> al = new ArrayList<>(Arrays.asList(3, 12, 13, 15));

        // Time Complexity: O(n * √m)
        // - n = number of elements in list
        // - m = average value of elements (for isPrime)
        // Space Complexity: O(1)
        // - In-place removal, no extra data structures used
        for (int i = 0; i < al.size(); i++)
            if (isPrime(al.get(i))) {
                al.remove(i);  // O(n) in worst case due to shifting
                i--;           // step back to check the new element at this index
            }

        System.out.println(al);
    }

    // Time Complexity: O(√num)
    // - Basic trial division up to sqrt(num)
    // Space Complexity: O(1)
    private static boolean isPrime(int num) {
        if (num <= 1) return false;  // Add this check to avoid 0 and 1 being considered prime
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0)
                return false;
        }
        return true;
    }
}

📊 Time and Space Complexity Table:

Case
Time Complexity
Space Complexity
Explanation
Best
O(n√m)
O(1)
Few or no elements are prime; minimal shifting in ArrayList.
Average
O(n√m + r·n)
O(1)
r primes in list cause r shifts (O(n) each), plus primality checks.
Worst
O(n²)
O(1)
All elements are prime → n removals, each causing O(n) shift.

n = number of elements in the list
m = average value of elements (for isPrime check)
r = number of primes in the list

Average Case: O(n√m + r·n) Time, O(1) Space


Where:


n = number of elements in the list


m = average value of elements (for checking prime)


r = number of prime numbers in the list





📌 What Happens Internally in the Original Code (Before Optimization)
1. Primality Check (isPrime)
Each call to isPrime(num) takes:
O(√m) time — because it checks divisibility up to √num
You check this for every element in the list:
n elements × O(√m) = O(n√m)



2. Removing Elements from ArrayList
This is the costly part.
Every time you do:
al.remove(i);

Java shifts all elements after index i to the left (by one position):
That shifting takes O(n) in the worst case (on average, O(n/2), but still linear)
Now imagine:
r out of n elements are prime
For each of those r primes, you call al.remove(i)
Each removal costs up to O(n) due to shifting, so total cost:
r × O(n) = O(r·n)