The way i see it this problem is a bit more complicated.
Say, for example the given no. is X = 2^3 * 3^5 ... Now if we want to
reduce X in the form M^N where both M and N > 1 then its not possible.
Hence, the actual problem reduces to finding not only the prime
factors but actual prime factorization.. i.e
Once X is factored in the form of p1^q1 * p2^q2 ..... * pN^qN ....
the question whether X can be factored in the form m^n depends on
whether the
GCD (q1, q2, q3, ... qN) > 1. If yes, then it can be expressed in the
form of m^n..
Just a slight modification to the above mentioned algos would solve
the problem...
To find the GCD of multiple elements we can use the following fact:
GCD(a, b, c) = GCD ( GCD(a,b) , c)... This can be extended to any no.
of elements.
Say, the input no. is X...
int uLmt = sqrt(X);
int currPowCnt = -1;
int GCD = -1;
for ( int i = 2; i <= uLmt; ++i)
{
currPowCnt = 0;
if (X % i == 0)
{
while (X % i == 0)
{
X /= i;
++currPowCnt;
}
GCD = (GCD == -1 ? currPowCnt : CalculateGCD(GCD, currPowCnt)) ;
/*
CalculateGCD is a method to calculate the GCD of 2 nos.
*/
// come out from the for loop as we don't need to process any
further...
if ( GCD == 1)
break;
}
}
if ( X > 1 || GCD == 1)
printf ("Not Possible");
else
printf ("Possible");
On Dec 26, 9:49 pm, top coder <[email protected]> wrote:
> Hello Samm
>
> I got your approach
>
> It seems it is not working for some of the examples
>
> Eg: N = 6
>
> 6 = 2X3 = 1X6 and hence it is not possible
> but your code prints "Yes possible".
>
> On Dec 26, 9:03 pm, SAMMM <[email protected]> wrote:
>
>
>
>
>
>
>
> > From Wht I can understand from problm to check whether N can be
> > expressed a m^n : Eg: 1331=11^3
>
> > What comes to my mind is to get all prime factors from 2 to SQRT(N)
> > [Prime Sieve] , Here N is the Given Integer .
>
> > Now Iterate over the prime number(p) from 2 to Sqrt(N)
> > do
> > T=N;
> > if(!(T%p)) while(!(T%p)) T/=p;
> > if(T==1) {printf("Yes possible");break;}
> > done
> > if (p>Sqrt(N)) printf("Not Possible");
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
