Sort By Primes - JAVA

// Author : Saurav Kalsoor
// Sort By Primes - JAVA

import java.util.*;

public class Test {

    static Scanner sc = new Scanner(System.in);
    public static void main(String[] args) {
        int n = sc.nextInt();

        ArrayList<Integer> arr = new ArrayList<>();

        for(int i=0; i < n; i++) {
            int input = sc.nextInt();
            arr.add(input);
        }

        ArrayList<Integer> result = sortPrimeNonPrime(arr, n);

        for(int i=0; i < n; i++)
            System.out.print(result.get(i) + " ");

        System.out.println();
    }

    public static ArrayList<Integer> sortPrimeNonPrime(ArrayList<Integer> arr, int n){

        int maxLimit = 10001;
        HashSet<Integer> primesSet = new HashSet<>();
        boolean[] isPrime = new boolean[maxLimit];

        for(int i=2; i < maxLimit; i++) isPrime[i] = true;

        for(int i=2; i < maxLimit; i++){
            if(isPrime[i]){
                primesSet.add(i);
                for(int j = i*i ; j < maxLimit; j += i)
                    isPrime[j] = false;
            }
        }

        ArrayList<Integer> primes = new ArrayList<Integer>();
        ArrayList<Integer> nonPrimes = new ArrayList<Integer>();

        for(int i=0; i < n; i++){
            if(primesSet.contains(arr.get(i))){
                primes.add(arr.get(i));
            }else{
                nonPrimes.add(arr.get(i));
            }
        }

        Collections.sort(primes);
        Collections.sort(nonPrimes, Collections.reverseOrder());

        ArrayList<Integer> result = new ArrayList<Integer>();

        int j = 0, k = 0;
        for(int i=0; i < n; i++){
            if(primesSet.contains(arr.get(i))){
                result.add(primes.get(j));
                j++;
            }else{
                result.add(nonPrimes.get(k));
                k++;
            }
        }

        return result;
    }
}