UVa : 10622 ( Perfect Pth Powers)

1st approch:- using gcd

1.
#include<bits/stdc++.h>
#include<cstring>
using namespace std;

#define nl printf("\n")
#define P(a) printf("%lld\n",a)
#define SP(a) printf("%lld ",a)
#define G(a) scanf("%lld",&a)
#define DB printf("I WAS HERE\n")
#define M 100000
long long gcd(long long a, long long b)
{
    if(a%b==0)
    {
        return b;
    }
    else
        return gcd(b,a%b);
}
long long a[M+1],p[9600],check[100],i,j,k,x;
void sieve()
{
    a[0]=1;a[1]=1;
    k=0;p[k]=2;
    k++;
    for(i=4;i<=M;i+=2)
    {
        a[i]=1;
    }
    for(i=3;i<=M;i+=2)
    {
        if(a[i]==0)
        {
            p[k]=i;
            k++;
            for(j=i*i;j<=M;j=j+2*i){
                a[j]=1;
            }
        }
    }
}
main()
{
    sieve();
    long long n;
    while(cin>>n)
    {
        if(n==0)
            break;
        long long ans,m=abs(n);
        x=sqrt(m);
        j=0;

        for(i=0;p[i]<=x;i++)
        {
            long long sum=0;
            if(m%p[i]==0)
            {
                while(m%p[i]==0)
                {
                    m=m/p[i];
                    sum++;
                }
                check[j]=sum;
                j++;
            }
        }

        if(m>1)
        {
            ans=1;
        }
        else if(m==1 && j==1)
        {
            ans=check[0];
        }
        else
            {
                sort(check,check+j);
                long long hold;
                hold=gcd(check[0],check[1]);
                for(i=2;i<j;i++)
                {
                    x=gcd(check[i],hold);
                    hold=x;
                }
                ans=hold;
            }
            if(n<0)
            {
                if(ans%2==0)
                {
                    while(ans%2==0)
                    {
                        ans=ans/2;
                    }
                }
            }
            P(ans);
    }

}

2nd approch by without using gcd

2.

#include<bits/stdc++.h>
using namespace std;
long long i;
long pow1(long long a,long long b)
{
    long long rslt=a;
    for(i=2;i<=b;i++)
    {
        rslt=rslt*a;
    }
    return rslt;
}
main()
{
    long long n;
    while(cin>>n)
    {
        long long n1,ans,power,sq,flag=0,i1,f=0;
        if(n==0)
            break;
        if(n<0)
        {
            flag=1;
            n1=n*-1;
        }
        else
            n1=n;
            sq=sqrt(n1);
            if(flag==1)
            {
                for(i1=-2;i1>=-sq;i1--)
                    {
                        ans=i1;
                        power=2;
                        while(ans>n)
                            {
                                ans=pow1(i1,power);
                                power++;
                            }
                        if(ans==n)
                          {
                              f=1;
                              cout<<power-1<<endl;
                              break;
                          }
                    }
                    if(f==0)
                cout<<1<<endl;
            }
        else if(flag==0)
        {
            for(i1=2;i1<=sq;i1++)
            {
                ans=i1;
                power=2;
                while(ans<n)
                {
                    ans=pow1(i1,power);
                    power++;
                }
                if(n==ans)
                {
                    f=1;
                    cout<<power-1<<endl;
                    break;
                }
            }
            if(f==0)
                cout<<1<<endl;
        }
    }
}