Hackerrank - Leonardo's Prime Factors Solution

Leonardo loves primes and created  queries where each query takes the form of an integer, . For each , he wants you to count the maximum number of unique prime factors of any number in the inclusive range  and then print this value on a new line.

Note: Recall that a prime number is only divisible by  and itself, and  is not a prime number.

Input Format

The first line contains an integer, , denoting the number of queries.
Each line  of the  subsequent lines contains a single integer, .

Constraints

Output Format

For each query, print the maximum number of unique prime factors for any number in the inclusive range  on a new line.

Sample Input

6
1
2
3
500
5000
10000000000

Sample Output

0
1
1
4
5
10

Explanation

1. The maximum number of unique prime factors of any number in the inclusive range  is , because  is not prime and its only factor is itself.
2. The maximum number of unique prime factors of any number in the inclusive range  is . We already know that the number  has  prime factors, but  has  prime factor (itself).
3. The maximum number of unique prime factors of any number in the inclusive range  is . The number  has  prime factor (itself), and we already know that the number  has  prime factor and the number  has  prime factors.
4. The maximum number of unique prime factors in the inclusive range  is . The product of our first four unique primes is , and there are no additional unique primes we can multiply that number by that results in a value .

Solution in Python

#!/bin/python3
import os
import sys
def prime(n):
    for i in range(2,n):
        if not n%i:
            return False
    return True
    
def primeCount(n):
    i= 2
    product =1
    count=0
    while True:
        if prime(i):
            product*=i
            if product>n:
                break
            count+=1
        i+=1
    return (count)
    
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    q = int(input())
    for q_itr in range(q):
        n = int(input())
        result = primeCount(n)
        fptr.write(str(result) + '\n')
    fptr.close()