#precomputing

This was a learning problem for me. I  knew that I have to calculate gcd in this problem. but i didn't knew that the answer will the least prime factor of gcd.

One approach to find that can be to iterate till the square root of that number and check for divisibility. the time limits were so that this solution would obviously be passed but since I am learning new things so I decide to go for precomputing that array using Sieve method

The function was:

int prime[100000];

void sieve(){

int i,j;

prime[0]=0;

for(i=1;i<=100000;i++)prime[i]=i;

for(i=2;<=sqrt(100000)+1;i++)

if(prime[i]==i){

for(j=2*i;j<=100000;j+=i)prime[j]=min(prime[j],i);}