- Leonardo's Prime Factors
Leonardo loves primes and created queries where each query takes the form of an integer, . For each , count the maximum number of distinct prime factors of any number in the inclusive range .
Note: Recall that a prime number is only divisible by and itself, and is not a prime number.
The maximum number of distinct prime factors for values less than or equal to is . One value with distinct prime factors is . Another is .
Complete the primeCount function in the editor below.
primeCount has the following parameters:
- int n: the inclusive limit of the range to check
- int: the maximum number of distinct prime factors of any number in the inclusive range .
The first line contains an integer, , the number of queries.
Each of the next lines contains a single integer, .
6 1 2 3 500 5000 10000000000
0 1 1 4 5 10
- is not prime and its only factor is itself.
- has prime factor, .
- The number has prime factor, , has and has prime factors.
- The product of the first four primes is . While higher value primes may be a factor of some numbers, there will never be more than distinct prime factors for a number in this range.