Given a number N, find the maximum number of unique prime factors any number can have in range [1, N].
Example 1:
Input:
N = 3
Output:
1
Explanation:
No number in the range 1 to 3
can have more than 1 unique
Prime factor. So, the Output is 1.
Example 2:
Input:
N = 500
Output:
4
Explanation:
No number in the range 1 to 500
can have more than 4 unique
Prime factors. So, the Output is 4.
An example of a number with 4
unique Prime Factors is 210.
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxUniquePrimeFactors() which takes an Integer N as input and returns the answer.
Expected Time Complexity: O(Largest Prime Factor of N)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 10^{18}

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3

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

Solutions:
class Solution:

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

	def maxUniquePrimeFactors(self, N):
		p = 1
		c = 0
		i = 2
		while p <= N:
			if self.isprime(i):
				p = p * i
				if p <= N:
					c += 1
			i += 1
		return c


class Solution:

	def maxUniquePrimeFactors(self, N):
		m = 100
		arr = [1] * (m + 1)
		arr[0] = 0
		arr[1] = 0
		i = 2
		while i * i <= m:
			if arr[i] == 1:
				for j in range(i * i, m + 1, i):
					arr[j] = 0
			i += 1
		c = 1
		cnt = 0
		for k in range(len(arr)):
			if arr[k] == 1:
				c = c * k
				if c <= N:
					cnt += 1
		return cnt
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.maxUniquePrimeFactors(N))