Remove Prime Optimised

Input:

10 13 14 15

Output:

[10, 14, 15]

package jan25;

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

public class RemovePrimes2 {
    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, m = value magnitude (for isPrime)
        // Space Complexity: O(1)
        // - In-place removal using Iterator
        Iterator<Integer> it = al.iterator();
        while (it.hasNext()) {
            int num = it.next();
            if (isPrime(num)) {
                it.remove(); // O(1) removal with iterator
            }
        }

        System.out.println(al);
    }

    // Time Complexity: O(√num), Space: O(1)
    private static boolean isPrime(int num) {
        if (num <= 1) return false;
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0)
                return false;
        }
        return true;
    }
}

📈 Final Complexity Table (Optimized)

Case	Time Complexity	Space Complexity	Explanation
Best	O(n√m)	O(1)	Efficient one-pass, no shifting
Average	O(n√m)	O(1)	All removals are O(1) using Iterator
Worst	O(n√m)	O(1)	Even if all elements are prime, no shifts