You are given a number 'n'. Your task is to check whether the power of its largest prime factor is greater than one or not.
Print "YES" if the power is greater than one otherwise print "NO".
Example 1:
Input: n = 36
Output: YES
Explaination: The largest prime which divides 
36 is 3. And it has power = 2 (2*2*3*3)
Example 2:
Input: n = 13
Output: NO
Explaintion: The largest prime which divides 
13 is 13 itself.
Your Task:
You do not need to read input or print anything. Your task is to complete the function largePrime() which takes n as input parameter and returns 1 if the largest prime which divides n has power greater than 1, else, returns 0.
Expected Time Complexity: O(log(n))
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ n ≤ 10^{18}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Number theory

Mathematics

Starter code: #User function Template for python3

class Solution:
    def largePrime(self, n):
        # code here

Solutions:
class Solution:

	def largePrime(self, n):
		i = 2
		d = {}
		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
		if d == {}:
			return 0
		if d[max(d)] > 1:
			return 1
		return 0


class Solution:

	def largePrime(self, n):

		def is_prime(n):
			i = 2
			while i * i <= n:
				if n % i == 0:
					return False
				i += 1
			return True
		if n < 2:
			return 0
		if is_prime(n):
			return 0

		def check(n):
			i = 2
			while i * i <= n:
				if n % i == 0:
					c = 0
					while n % i == 0:
						n = n // i
						c += 1
				i += 1
			if n != 1:
				return False
			if c > 1:
				return True
			else:
				return False
		if check(n):
			return 1
		return 0