HackerEarth Array Formation Liv.ai problem solution

In this HackerEarth Array Formation Liv.ai problem solution, You are given an array A of n integers. You have to make a queue and stack 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.

HackerEarth Array Formation Liv.ai problem solution.

#include<bits/stdc++.h>
#define LL long long int
#define M 1000000007
#define reset(a) memset(a,0,sizeof(a))
#define rep(i,j,k) for(i=j;i<=k;++i)
#define per(i,j,k) for(i=j;i>=k;--i)
#define print(a,start,end) for(i=start;i<=end;++i) cout<<a[i];
#define endl "\n"
LL pow(LL a,LL b,LL m){LL x=1,y=a;while(b > 0){if(b%2 == 1){x=(x*y);if(x>m) x%=m;}y = (y*y);if(y>m) y%=m;b /= 2;}return x%m;}
LL gcd(LL a,LL b){if(b==0) return a; else return gcd(b,a%b);}
LL gen(LL start,LL end){LL diff = end-start;LL temp = rand()%start;return temp+diff;}
using namespace std;
bool p[1000001];
int a[1000001];
vector<int> q , s;
int main()
    {
        ios_base::sync_with_stdio(0);
        for(int i = 2; i <= 1000000 ; i++)
            {
                if(p[i] == 0)
                    {
                        for(int j = 2 * i; j <= 1000000 ; j+=i)
                            {
                                p[j] = 1;
                            }
                    }
            }
        int n;
        cin >> n;
        for(int i = 1; i <= n ; i++)
            {
                cin >> a[i];
                assert(a[i] > 1);
                if(p[a[i]] == 0)
                    {
                        q.push_back(a[i]);
                    }
                else
                        s.push_back(a[i]);
            }
        reverse(s.begin() , s.end());
        for(int i: q)
            cout << i << " ";
        cout << endl;
        for(int i: s)
            cout << i << " ";

    }

Second solution

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    bool p[1000005]={0};
    p[0]=p[1]=1;
    for(int i=2;i<=1000000;i++)
    {
        if(!p[i])
        {
            for(int j=2*i;j<=1000000;j+=i)
                p[j]=1;
        }
    }
    vector<int>s,q;
    for(int i=0;i<n;i++)
    {
        int temp;
        cin>>temp;
        if(!p[temp])
            q.push_back(temp);
        else s.push_back(temp);
    }
    for(int i=0;i<q.size();i++)cout<<q[i]<<" ";
    cout<<"\n";
    for(int i=s.size()-1;i>=0;i--)cout<<s[i]<<" ";
    return 0;
}