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 <topcode...@gmail.com> 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 <somnath.nit...@gmail.com> 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.