Leonardo loves primes and created \(q\) queries where each query takes the form of an integer, \(n\). For each \(n\), he wants you to count the maximum number of unique prime factors of any number in the inclusive range \([1,n]\) and then print this value on a new line. Note: Recall that a prime number is only divisible by \(1\) and itself, and \(1\) is not a prime number.
Input Format
The first line contains an integer, \(q\), denoting the number of queries. Each line \(i\) of the \(q\) subsequent lines contains a single integer, \(n\).
Constraints
- \(1\leq q\leq 10^5\)
- \(1\leq n\leq 10^{18}\)
Output Format
For each query, print the maximum number of unique prime factors for any number in the inclusive range \([1,n]\) on a new line.
Solution
In order to maximize the unique number of primes, we multiply each prime in ascending order until the given limit is reached. Since we take each prime number into account only once, i.e. with exponent \(1\), and step up to the next larger prime, the overall number of distinct prime factors gets maximized. A simple implementation in Python is then:
def primeCount(n):
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53]
p = 1
i = 0
while True:
p*= primes[i]
if p > n:
return i
i+= 1
return 0