Can you tell me what's wrong in my code. Sieve implementation is correct, and play() method is pretty straight-forward too

#1

import java.util.*;

public class Main
{
final static double MAX = 1000000 ;
static boolean prime[] = new boolean [(int) (MAX + 1.0)] ;
static int n;
static int q;
static List<Stack> a;
static List<Stack> b;
static int[] firstQ;

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

    a = new ArrayList<Stack<Integer>>();
    b = new ArrayList<Stack<Integer>>();

    //create q stacks each
    for(int i=0; i<=q; i++){
        a.add(new Stack<>());
        b.add(new Stack<>());
    }

    for(int i=0; i<n; i++)
        a.get(0).push(sc.nextInt());

    SieveOfEratosthenes();
    firstQ = getFirstNprime(q);
    //System.out.println(firstQ[5]);

   play();

}

private static void play()
{
    for(int i=0; i<q; i++)
    {
        while(!a.get(i).isEmpty()) {
            int x = a.get(i).pop();
            if(x%firstQ[i+1]==0) //if divisible by ith prime number
                b.get(i+1).add(x);
            else
                a.get(i+1).add(x);
        }
    }

// System.out.println(a.get(q));
// System.out.println(b.get(q));
while(!b.get(q).isEmpty())
System.out.println(b.get(q).pop());
while(!a.get(q).isEmpty())
System.out.println(a.get(q).pop());

}

private static int[] getFirstNprime(int q) {
    int count = 1, num = 1;
    int[] a = new int[q+1];

    while (count <= q)
    {
        // if the number is prime add it
        if (prime[num]) {
            a[count] = num;
            count++;
        }
        // get to next number
        num++;
    }
    return a;
}

static void SieveOfEratosthenes()
{

    for(int i = 0; i <= MAX; i++)
        prime[i] = true ;

    prime[1] = false;

    for (int p = 2; p * p <= MAX; p++) {

        // If prime[p] is not changed, then it is a prime
        if (prime[p] == true) {

            // Set all multiples of p to non-prime
            for (int i = p * 2; i <= MAX; i += p)
                prime[i] = false;
        }
    }
}

}

#2

Consider input:
5 2
1 2 3 4 5
Expected Output:
2
4
3
5
1
Your o/p:
3
5
1
debug for this

Crosscheck the approach and the logic:

  • A simple approach would be to simply make two arrays of stacks and solve as guided. We can precompute the primes using sieve to save time. This approach will take a lot of space as the sizes of arrays will be size = q+1.

  • for a better approach While this algorithm takes almost same time, it saves a lot of space.
    If we look at our algorithm more closely , you will notice that at any point , we only need 3 stacks atmost.

    1. Stack S from which we are popping elements. This is equivalant to stack a[i-1] from the previous method.
    2. Stack A to which we will be pushing the elements in case they are not divisible by ith prime number. This is equivalant to stack a[i] from the previous method.
    3. Stack B to which we will be pushing the elements in case they are divisible by ith prime number. This is equivalant to stack b[i] from the previous method.

    After each iteration , make S = A for the next iteration since for the next iteration we will be popping elements out from the stack that is currently A.

    After each iteration , we pop and push all elements from B to a queue to maintain the order which would otherwise have been maintained by having different arrays of stack.

This approach requires a lot less space than the previous approach and is thus better.