Hackerrank Solution: Leonardo's Prime Factors

Original Problem

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

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

« Back to problem overview