Editorial for Prima Sort

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

For each element of \(A\), we can find the primes that can divide it by trying to divide that number with each number up to the square root of that number. The minimum of the primes determines the list to which that element belongs.

Now we need to iterate all the primes and print each of the lists consequently. It should be not forgotten to sort each list before printing that list.

#include <bits/stdc++.h>

using namespace std;

const int md = (int) 1e9 + 7;
const int siz = 300005;

set<int> numbers;
long long n, m, k, l, a;
map<int, vector<int>> ma;

int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a;
        int f=1;
        for(int j=2;j<=sqrt(a);j++){
            if(a%j==0){
                f=0;
                ma[j].push_back(a);
                numbers.insert(j);
                break;  
            }
        }
        if(f) {
            ma[a].push_back(a);
            numbers.insert(a);
        }
    }

    for(auto x:numbers){
        vector<int> k=ma[x];
        sort(k.begin(), k.end());
        for(auto y:k){
            cout<<y<<' ';
        }
    }

}