Array Formation

You are given an array A of n integers. You have to make a queue and stack of the given integers. The queue should contain only prime numbers and the stack should contain only composite numbers. All numbers in the array will be >1.

The rule to form the stack and queue is that you should be able to generate the array using the pop and dequeue operations.
Note : Please read this explanation carefully

Let the array A contains 5 integers : 7 , 21 , 18 , 3 , 12 then the content of queue and stack will be :
Queue : 7 , 3
Stack : 12 , 18 , 21
Now if you follow the rules of stack and queue then you see that you can generate the array using the pop operations of stack and dequeue operation of queue as follows :

dequeue from queue : 7
pop from stack : 7 , 21
pop from stack : 7 , 21 , 18
dequeue from queue : 7 , 21 , 18 , 3
pop from stack : 7 , 21 , 18 , 3 , 12

Thus for every array A you have to print the contents of queue in the first line and contents of stack in the second line.

Example:

Input:  n = 5, a = [7,21,18,3,12]

Output:

7 3 
12 18 21 

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

bool prime[1000001];
void primeInitialize()
{

    memset(prime, true, sizeof(prime));
    prime[0] = false;
    prime[1] = false;
    for (int i = 2; i * i <= 1000001; i++)
    {
        if (prime[i])
        {
            for (int j = i * i; j <= 1000001; j += i)
                prime[j] = false;
        }
    }
}

void arrayFormation(int n, int a[])
{
    stack<int> st;
    queue<int> q;

    for (int i = 0; i < n; i++)
    {
        if (prime[a[i]])
            q.push(a[i]);
        else
            st.push(a[i]);
    }
    while (!q.empty())
    {
        int x = q.front();
        cout << x << " ";
        q.pop();
    }
    cout << "\n";
    while (!st.empty())
    {
        int x = st.top();
        cout << x << " ";
        st.pop();
    }
    cout << "\n";
}
int main()
{
    int n = 5;

    int a[n] = {7, 21, 18, 3, 12};

    primeInitialize();

    arrayFormation(n, a);

    return 0;
}