find two divisors of a number, such that the gcd of the sum of those divisors and the number equals 1

Problem statement you are given an array. you have to find two divisors other than 1, (d₁,d₂) for each element, ai, such that gcd of the sum of those two divisors and the element is 1(gcd(d₁+d₂, a_i)=1). if not possible for some element then let the divisors be -1 and -1 in that case. In Codeforces

Constraints: 1<= elements range <=10⁷ and array size<10⁵

Solution: The gcd(d₁+d₂, a_i ) equals 1 only when d₁ +d₂ and ai do not have any common factor. As d₁ and d₂ both are factors of ai, if there is some common factor in d₁ and d₂, then the greatest among those will be equals to gcd(d_1+d2, a_i).

see, in this case, let p be the largest common factor of d1 and d2, then
d₁=p*r₁ and d₂ =p*r₂
d₁+d₂ =p(r₁+r₂ )
as d₁ and d₂ are divisors of a_i p will also be one of the divisors
so, gcd(p(r₁+r₂ ),a_i)=p

so, you have to divide all the prime factors of ai into two sets such that there is no common factor between them, and this is only be done if there is more than one prime number as a factor by separating them in such a way there is no such prime number that occurs in both the sets.

how this can be implemented?
Well, we can check whether the element has more than one prime number as a factor in O(log N) time iff we know at least one prime factor. ( how? leaving it as your brain charger). Now, how will we get at least one prime factor in constant time? well, we need to pre-process the lowest prime factor for each number between 1 and 10^7 by using the SeiveOfErathrones technique, which will calculate it in O(nloglogn) time complexity.

we have the least prime factor. now what? we can now divide the number with this factor until it is divisible and greater than 1. if it stops at 1 then there is only one prime number as a factor, obviously the answer will be (-1,-1)
otherwise, we can divide the number by this method, whatever the number left after dividing with the smallest prime factor is one divisor,d1, as it does not contain the smallest prime divisor of ai. and another will be consist of all smallest prime number, that can be easily calculated by ai/previously generated divisor(d1). d2=ai/d1.
If the element is itself is a prime number then obviously answer will be -1,-1.

here is the c++ implementation.

/*
 * Created by me on 24-11-2021.
 */
#include <bits/stdc++.h>
#define F(a,c) for (ll a=0;a<c; a++)
#define ll long long
#define V(x) vector<x>
using namespace std;

/*
 * storing smallest prime factor in prime[] using  SieveOfEratosthenes
 */
ll const prime_upto=10000005;
ll smallest_prime_factor[prime_upto + 1]={0};
void SieveOfEratosthenes(ll n=prime_upto)
{
    for (ll p = 2; p * p <= n; p++)
        if (!smallest_prime_factor[p])
            for (ll i = p * p; i <= n; i += p)
                if(!smallest_prime_factor[i])smallest_prime_factor[i]=p;
    
}
/*
 * main function / driver function
 */
int main(){
    SieveOfEratosthenes();
    ll n,a,b;
    cin>>n;
    V(ll) arr(n+1),arr2(n+1);//to store divisors d1 & d2 in different array
    F(i,n){//iterating through elements
        cin>>a;
        if(!smallest_prime_factor[a]){//if element is prime
            arr[i]=-1;
            arr2[i]=-1;
        }else{//if element is not prime
            b=a;
            while(b%smallest_prime_factor[a]==0){//dividing with smallest prime factor iff divisible
                b/=smallest_prime_factor[a];
            }
            if(b==1){//only consist of the smallest prime factor
                arr[i]=-1;
                arr2[i]=-1;
            }else{//can be divisible
                arr[i]=b;//one divisor is the left over number after dividing with smallest prime factor
                arr2[i]=a/b;//another number is the element divided by the previouly found divisor
            }
        }
    }

    //printing divisor array as output 
    F(i,n)cout<<arr[i]<<" ";cout<<endl;
    F(i,n)cout<<arr2[i]<<" ";cout<<endl;
    return 0;
}

sample input

10
2 3 4 5 6 7 8 9 10 24

sample output

-1 -1 -1 -1 3 -1 -1 -1 2 2 
-1 -1 -1 -1 2 -1 -1 -1 5 3

let me know if there is any suggestion/ improvement/ comments in the section below. I would love to hear from you.