As we know that every number >=2 can be represented as natural powers of primes(prime factorization). Also prime factorization is unique for a number. 
Eg. 360 = 2^{3}3^{2}5^{1}
Today we are interested in geek numbers. A geek number is a number whose prime factorization only contains powers of unity.Below are some geek numbers.
Eg. 2 = 2^{1}
    22 = 2^{1}11^{1}
Example 1:
Input: N = 22
Output: Yes
Explaination: 22 = 2^{1}11^{1}. Where all the 
powers of prime numbers are one.
Example 2:
Input: N = 4
Output: No
Explaination: 4 = 2^{2}. Where all the 
powers of all the prime are not one.
Your Task:
You do not need to read input or print anything. Your task is to complete the function geekNumber() which takes N as input parameter and returns 1 if it a geek number. Otherwise, returns 0.
Expected Time Complexity: O(sqrt(N))
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Number theory

Mathematics

Starter code: #User function Template for python3

class Solution:
    def geekNumber(self, N):
        # code here

Solutions:
class Solution:

	def geekNumber(self, n):
		if n in [1, 2, 3]:
			return 1
		k = int(n ** 0.5 + 0.5)
		for i in range(2, k + 1):
			if n % i == 0:
				if n % i ** 2 == 0:
					return 0
		return 1


class Solution:

	def geekNumber(self, N):
		if N == 1:
			return 1
		elif N == 2 or N == 3:
			return 1
		d = {}
		i = 2
		while i * i <= N:
			while N % i == 0:
				if i in d:
					d[i] += 1
				else:
					d[i] = 1
				N = N // i
			i += 1
		if N > 1:
			if N in d:
				d[N] += 1
			else:
				d[N] = 1
		for key in d:
			if d[key] != 1:
				return 0
		return 1


class Solution:

	def geekNumber(self, N):
		for i in range(2, int(N ** 0.5) + 1):
			if N % i == 0:
				N //= i
				if N % i == 0:
					return 0
		return 1


class Solution:

	def geekNumber(self, n):
		c = 0
		while n % 2 == 0:
			c += 1
			n = n // 2
		if c > 1:
			return 0
		i = 3
		while i <= n ** 0.5:
			c = 0
			while n % i == 0:
				c += 1
				n = n // i
			if c > 1:
				return 0
			else:
				i += 2
		return 1


class Solution:

	def geekNumber(self, N):
		i = 2
		while i * i <= N:
			if N % i == 0:
				N //= i
			if N % i == 0:
				return 0
			else:
				i += 1
		return 1


import math

class Solution:

	def geekNumber(self, N):

		def check(num):
			if num == 2:
				return True
			for i in range(3, int(math.sqrt(num)) + 1):
				if num % i == 0:
					return False
			return True
		for i in range(2, int(math.sqrt(N)) + 1):
			p = 0
			if N % i == 0 and check(i):
				p = 1
				if int(N / i) % i == 0:
					return 0
		return 1


class Solution:

	def geekNumber(self, num):
		mp = {}
		i = 2
		while i * i <= num:
			if num % i == 0:
				if mp.__contains__(i):
					mp[i] += 1
				else:
					mp[i] = 1
				d = num // i
				if mp.__contains__(d):
					mp[d] += 1
				else:
					mp[d] = 1
				num = num // i
			else:
				i += 1
		for k in mp:
			if mp[k] > 1:
				return False
		return True


class Solution:

	def geekNumber(self, N):
		m = {}
		i = 2
		K = N
		while i * i <= K:
			while N % i == 0:
				if i in m:
					return 0
				else:
					m[i] = 1
				N = N // i
			i += 1
		if N != 1:
			if i in m:
				return 0
		return 1


class Solution:

	def geekNumber(self, N):
		i = 2
		while i * i <= N:
			c = 0
			n = N
			while n % i == 0:
				n = n / i
				c += 1
			if c > 1:
				return 0
			i += 1
		return 1


class Solution:

	def geekNumber(self, n):
		import math
		count = 0
		while n % 2 == 0:
			count += 1
			n = n / 2
			if count >= 2:
				return 0
		for i in range(3, int(math.sqrt(n)) + 1, 2):
			count = 0
			while n % i == 0:
				count += 1
				n = n / i
				if count >= 2:
					return 0
		return 1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		if ob.geekNumber(N) == 1:
			print('Yes')
		else:
			print('No')


class Solution:

	def geekNumber(self, N):
		for i in range(2, N):
			if i * i > N:
				break
			c = 0
			while N % i == 0:
				N //= i
				c += 1
			if c > 1:
				return 0
		return 1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		if ob.geekNumber(N) == 1:
			print('Yes')
		else:
			print('No')


import math

class Solution:

	def geekNumber(self, n):
		l = []
		cnt = 0
		res = 1
		for i in range(2, int(math.sqrt(n)) + 1):
			while n % i == 0:
				l.append(i)
				n = n // i
		if n > 2:
			l.append(n)
		for i in l:
			if l.count(i) == 1:
				cnt += 1
		if cnt == len(l):
			return 1
		else:
			return 0
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		if ob.geekNumber(N) == 1:
			print('Yes')
		else:
			print('No')


import math

class Solution:

	def geekNumber(self, N):
		k = int(math.sqrt(N))
		i = 2
		count = 0
		while N != 0 and i <= k:
			if N % i == 0:
				count += 1
				N = N // i
				i = i - 1
			else:
				count = 0
			if count >= 2:
				return 0
			i += 1
		return 1


from math import sqrt

class Solution:

	def geekNumber(self, N):
		x = int(sqrt(N)) + 1
		for i in range(2, x):
			if N % i == 0:
				N = N / i
			if N % i == 0:
				return 0
		return 1


import math
from collections import Counter

class Solution:

	def geekNumber(self, N):
		c = []
		temp = N
		while temp % 2 == 0:
			c.append(2)
			temp = temp // 2
		for i in range(3, int(math.sqrt(N) + 1)):
			while temp % i == 0:
				c.append(i)
				temp = temp // i
		dic = Counter(c)
		for i in dic.values():
			if i > 1:
				return 0
		return 1


import math

class Solution:

	def geekNumber(self, N):
		l = {}
		for i in range(int(math.sqrt(N) + 1)):
			l[i] = 0
		cnt = 0
		while N % 2 == 0:
			cnt += 1
			l[2] = cnt
			N = N / 2
		cnt = 0
		for i in range(3, int(math.sqrt(N)) + 1, 2):
			while N % i == 0:
				cnt += 1
				l[i] = cnt
				N = N / i
			cnt = 0
		li = l.keys()
		lo = l.values()
		if N > 2:
			l[N] = 1
		for x in lo:
			if x > 1:
				return 0
			else:
				continue
		return 1


class Solution:

	def geekNumber(self, N):
		div = 2
		while div * div <= N:
			counter = 0
			while N % div == 0:
				counter += 1
				N = N // div
			div += 1
			if counter > 1:
				return 0
		return 1


import math

class Solution:

	def geekNumber(self, N):
		total = 0
		while N % 2 == 0:
			total += 1
			N = N / 2
		if total > 1:
			return 0
		total = 0
		for i in range(3, int(math.sqrt(N)) + 1, 2):
			total = 0
			while N % i == 0:
				N = N / i
				total += 1
			if total > 1:
				return 0
		return 1


import math

class Solution:

	def geekNumber(self, n):
		for i in range(2, int(math.sqrt(n)) + 1):
			c = 0
			while n % i == 0:
				n = n / i
				c += 1
				if c == 2:
					return 0
		return 1


class Solution:

	def geekNumber(self, N):
		if N % 4 == 0:
			return False
		for i in range(3, int(N ** 0.5) + 1, 2):
			if N % i == 0:
				N /= i
			if N % i == 0:
				return False
		return True


class Solution:

	def geekNumber(self, N):
		for i in range(2, int(pow(N, 0.5)) + 1):
			c = 0
			while c <= 2 and N % i == 0:
				N = N / i
				c += 1
			if c > 1:
				return 0
		return 1


class Solution:

	def geekNumber(self, N):
		import math
		factors = []
		while N % 2 == 0:
			factors.append(2)
			N = N / 2
		for i in range(3, int(math.sqrt(N)) + 1, 2):
			while N % i == 0:
				factors.append(i)
				N = N / i
		if N > 2:
			factors.append(N)
		return len(set(factors)) == len(factors)


class Solution:

	def geekNumber(self, N):
		from math import sqrt
		sq = int(sqrt(N))
		primefactor = []
		while N % 2 == 0:
			primefactor.append(2)
			N = N / 2
		for i in range(3, sq + 1, 2):
			while N % i == 0:
				primefactor.append(i)
				N = N / i
		if N > 2:
			primefactor.append(N)
		st = set(primefactor)
		if len(st) == len(primefactor):
			return 1
		else:
			return 0


class Solution:

	def geekNumber(self, N):
		c = 2
		while c * c <= N:
			pow = 0
			while N % c == 0:
				N //= c
				pow += 1
			if pow > 1:
				return 0
			c += 1
		return 1


import math

class Solution:

	def geekNumber(self, n):
		if n <= 1:
			return 1
		c = 0
		while n % 2 == 0:
			c += 1
			n //= 2
		if c > 1:
			return False
		c = 0
		while n % 3 == 0:
			c += 1
			n //= 3
		if c > 1:
			return False
		for i in range(5, int(math.sqrt(n)) + 1, 6):
			c = 0
			while n % i == 0:
				c += 1
				n //= i
			if c > 1:
				return False
			c = 0
			while n % (i + 2) == 0:
				c += 1
				n //= i + 2
			if c > 1:
				return False
		return True


import math

class Solution:

	def geekNumber(self, N):
		if N == 1:
			return 1
		end = int(math.sqrt(N))
		flag = False
		count = 0
		for i in range(2, end + 1, 1):
			while N % i == 0:
				N = N / i
				count += 1
			if count > 1:
				flag = True
				break
			count = 0
		if flag:
			return 0
		return 1


class Solution:

	def geekNumber(self, N):
		p = 2
		while p * p <= N:
			n = N
			count = 0
			while n % p == 0:
				count += 1
				n //= p
			if count > 1:
				return 0
			p += 1
		return 1


class Solution:

	def is_prime(self, n):
		if n == 2 or n == 3:
			return True
		for i in range(2, int(n ** (1 / 2)) + 1):
			if n % i == 0:
				return False
		return True

	def geekNumber(self, N):
		if N < 4:
			return True
		c = 0
		i = 2
		for i in range(2, int(N ** (1 / 2)) + 1):
			t = 0
			while N % i == 0:
				N //= i
				t += 1
				if t > 1:
					return False
		return True


import math

class Solution:

	def geekNumber(self, N):
		a = []
		while N % 2 == 0:
			if 2 in a:
				return False
			else:
				a.append(2)
				N = N / 2
		while N % 3 == 0:
			if 3 in a:
				return False
			else:
				a.append(3)
				N = N / 3
		for i in range(5, int(math.sqrt(N)) + 1, 6):
			while N % i == 0:
				if i in a:
					return False
				else:
					a.append(i)
					N = N / i
			while N % (i + 2) == 0:
				if i + 2 in a:
					return False
				else:
					a.append(i + 2)
					N = N / (i + 2)
		return True


class Solution:

	def geekNumber(self, N):
		if N > 3 and N % 4 == 0:
			return 0
		if N > 8:
			if N % 9 == 0:
				return 0
			for k in range(1, int((N ** 0.5 + 7) // 6)):
				if N % (6 * k - 1) ** 2 == 0:
					return 0
				if N % (6 * k + 1) ** 2 == 0:
					return 0
		return 1


import math

class Solution:

	def geekNumber(self, n):
		count = 0
		while n % 2 == 0:
			count = count + 1
			n = n / 2
		if count > 1:
			return 0
		else:
			count = 0
		prev = 3
		for i in range(3, int(math.sqrt(n)) + 1, 2):
			while n % i == 0:
				n = n / i
				if prev == i:
					count = count + 1
				else:
					prev = i
					count = 1
			if count > 1:
				return 0
		return 1


import math

class Solution:

	def geekNumber(self, N):
		if N == 1:
			return True
		for i in range(2, int(math.sqrt(N) + 1)):
			if N % i == 0:
				N = N / i
			if N % i == 0:
				return False
				break
		return True


class Solution:

	def geekNumber(self, N):
		x = N
		i = 2
		if N == 1:
			return 1
		while int(i * i) <= N:
			count = 0
			while x % i == 0:
				count += 1
				x //= i
			i += 1
			if count > 1:
				return 0
		return 1


import math as m

class Solution:

	def geekNumber(self, N):
		lst = []
		while N % 2 == 0:
			lst.append(2)
			N /= 2
		for i in range(3, int(m.sqrt(N)) + 1, 2):
			while N % i == 0:
				lst.append(i)
				N /= i
		if N >= 2:
			lst.append(N)
		x = len(lst)
		y = len(set(lst))
		if x == y:
			return 1
		else:
			return 0


from math import sqrt

class Solution:

	def geekNumber(self, n):
		cont = 0
		while n % 2 == 0:
			cont += 1
			n /= 2
			if cont == 2:
				return 0
		for i in range(3, int(sqrt(n)) + 1, 2):
			cont = 0
			while n % i == 0:
				cont += 1
				n /= i
				if cont == 2:
					return 0
		return 1


import math

class Solution:

	def geekNumber(self, N):
		i = 2
		while i * i <= N:
			c = 0
			while N % i == 0:
				c += 1
				N = N // i
				if c > 1:
					return 0
			i += 1
		return 1


import numpy as np
ar = np.ones((1000001,), dtype=int) * -1

def sieve():
	maxN = 1000000
	for i in range(2, maxN + 1):
		if ar[i] == -1:
			ar[i] = i
			for j in range(i * i, maxN + 1, i):
				if ar[j] == -1:
					ar[j] = i

class Solution:

	def geekNumber(self, N):
		if N == 1:
			return 1
		for i in range(2, int(N ** (1 / 2) + 1)):
			if N % i == 0:
				N = N // i
				if N % i == 0:
					return 0
		return 1


import numpy as np
ar = np.ones((1000001,), dtype=int) * -1

def sieve():
	maxN = 1000000
	for i in range(2, maxN + 1):
		if ar[i] == -1:
			ar[i] = i
			for j in range(i * i, maxN + 1, i):
				if ar[j] == -1:
					ar[j] = i
sieve()

class Solution:

	def geekNumber(self, N):
		counter = 0
		last_pf = None
		while N > 1:
			current_pf = ar[N]
			N = N // current_pf
			if last_pf is None:
				last_pf = current_pf
				counter = 1
			elif current_pf != last_pf:
				if counter > 1:
					return 0
				last_pf = current_pf
				counter = 1
			else:
				counter += 1
		else:
			if counter > 1:
				return 0
		return 1