FactorulX

#include <fstream>
#include <algorithm>
#define LL long long int
using namespace std;
int N,Fact[500500];

LL CMMDC(int a,int b)
{
    int r;
    if(a==0&&b==0)
        return -1;
    else
    {
        if(a<b)
            swap(a,b);
        if(b==0)
            return a;
        else
        {
            r=a%b;
            while(r)
                a=b,b=r,r=a%b;
            return b;
        }
    }
}

bool cautbin(int x)
{
    int st=0,dr=N;
    while(st<=dr)
    {
        int m=(st+dr)/2;
        if(Fact[m]==x)
            return false;
        if(Fact[m]>x)
            dr=m-1;
        if(Fact[m]<x)
            st=m+1;
    }
    return true;
}

int factorx(int n)
{
    int factx=1;
    if(n%2==0)
    {
        factx*=2;
        while(n%2==0)
            n/=2;
    }
    int d=3;
    while(n>1)
    {
        if(n%d==0)
        {
            factx*=d;
            while(n%d==0)
                n/=d;
        }
        else
            d+=2;
        if(n>1&&d*d>n)
        {
            factx*=n;
            break;
        }
    }
    return factx;
}

int main()
{
    int n;
    ifstream f("factorulx.in");
    f>>n;
    int a[n];
    for(int i=0;i<n;++i)
        f>>a[i];
    for(int i=0;i<n-1;++i)
        for(int j=i+1;j<n;++j)
        {
            LL cmmdc=CMMDC(a[i],a[j]);
            bool ok=false;
            if(cmmdc==1LL*a[i]*a[j])
            {
                if(cautbin(1))
                    ok=true,Fact[N++]=1;
            }
            else
            {
                int factx=factorx(cmmdc);
                if(cautbin(factx))
                    ok=true,Fact[N++]=factx;
            }
            if(ok)
                sort(Fact,Fact+N);
        }
    ofstream g("factorulx.out");
    g<<N<<'\n';
    for(int i=0;i<N;++i)
        g<<Fact[i]<<' ';
    g<<'\n';
    return 0;
}