Express as a power b


sqrt(n) approach fails can any one tell how it is done…???


sorry link is not working but i have updated once see again…??

In my opinion ,

if n is prime then answer is No
else do the prime factorization of n and store the prime factor as many time they appear if all the factors are same then print Yes else No

Let n=16 prime factors [2,2,2,2] here all prime factors are same so Yes
let n=15 prime factors [3,5] here all prime factors are different so No
let n=31 this is a prime number hence No

PS: I’m still learning I don’t know it works or not but give it a try and let me know the result

1 Like

Close but incorrect. You actually want the gcd of the number of occurrences of each factor to be greater than 1. For example, n = 36 would give a No by your method.

1 Like

Thank you, but i think it wont work factors can be different Like 36,100 has prime factors [2,2,3,3],[2,2,5,5] and can be express as a power b right…???

Yeah, and sqrt(n) method will also not work

Okay Got it thanks sir @rathi_22

One method is to iterate over b = 2 to log(n) and see if the largest integer a such that a^b <= n is a b-th root of n. This is O(log^2(n)) and should pass within the TL. Just to clarify you can find a in O(log(n)) using binary search.

An additional optimization is to just iterate over primes in 2 to log(n) (~25) which will further improve the constant factor by roughly 2.5

I guess you’re getting TLE.
I’d prefer to precompute over the constraint and later directly print the respective answer for the test cases.