question:
sqrt(n) approach fails can any one tell how it is done…???
Thanks…!
404 PAGE NOT FOUND
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
examples:
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
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.
import math
def get(n):
p=set()
for i in range(2,int(math.sqrt(n))+1):
pwr=i*i
while pwr<=n:
p.add(pwr)
pwr*=i
return p
def main():
n=int(input())
l=[]
for _ in range(n):
l.append(int(input()))
maxi=max(l)
precomp=get(maxi)
for i in l:
if i in precomp:
print("Yes")
else:
print("No")
main()