NFACTOR

Hard
0/120
Average time to solve is 50m
profile
Contributed by
11 upvotes
Asked in companies
AppleMicrosoftPayPal

Problem statement

You have given ‘Q’ queries where each query is represented by three positive integers ‘A’, ‘B’ and ‘N’. For each query, you are supposed to find the number of integers in the range [A, B] which has exactly ‘N’ unique prime factors.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line contains an integer ‘Q’ denoting the number of queries.

The next ‘Q’ lines contain three space-separated integers ‘A’, ‘B’ and ‘N’ which are described in the problem statement.

Output Format :

For each query, print the number of integers in the range [A, B] which has exactly ‘N’ unique prime factors. 


The output of each query will be printed in a separate line.

Note:

You are not required to print the expected output, it has already been taken care of. Just implement the function.

Constraints :

1 <= Q <= 10000
1 <= A, B <= 10000
1 <= N <= 10

Where ‘Q’ is the number of queries and ‘A’, 'B’ and ‘N’ are three integers as described in the problem statement.

Time limit: 1 sec

Sample Input 1 :

2
3 8 2
1 8 1

Sample output 1 :

1
6

Explanation of Sample output 1 :

For the first test case, 6 is the only integer in the range [3, 8] which has exactly 2 unique prime factors, 2 and 3.

For the second test case, [2, 3, 4, 5, 7, 8] will have exactly 1 unique prime factor.

Sample Input 2 :

2
1 10 3
1 2 1

Sample output 2 :

0
1

Explanation of Sample output 2 :

For the first test case, there is no number in the range [1, 10] which has 3 unique prime factors.

For the second test case, 2 has 1 unique prime factor.
Hint

Can you think of checking each integer in the given range?

Approaches (3)
Brute force

The basic idea of this approach is to iterate through each integer in the given range for each query and check the number of unique prime factors.

 

Let us try to implement a function primeFactors(int n) which returns the number of unique prime factors for a given integer. 

 

 

Algorithm:

 

  1. Create a variable “count” and initialize it to 0 to store the count of prime factors.
  2. Start a loop using a variable ‘i’ such that 2 <= i <= sqrt(n). Here sqrt(n) means square root of n.
    • Now, keep dividing ‘n’ while it is still divisible by ‘i’.
      • Divide “n” by “i” i.e. do n = n / i.
      • Increment the “count” as count = count + 1.
  3. Now, if “n” is greater than 1 then increment the count by 1.
  4. Return “count”.

 

Now consider the following steps for finding the answer for each query.

 

  1. Create a variable “ans” and initialize it to 0 which stores the answer of the current query.
  2. Iterate through each integer in the range [A, B].
    • Get the count of unique prime factors from the function primeFactors()
    • If the number of prime factors of the current integer is equal to ‘N’ then increment the “ans” by 1.
  3. Return “ans”.

 

Time Complexity

O(Q * (B - A) * sqrt(B)), where ‘Q’ denotes the number of queries and ‘A’ and ‘B’ denotes the given integer.

 

We are iterating through each query and then for each query, we are finding the number of prime factors for each integer in the range [A, B].  Since, primeFactors(int N) takes O(sqrt(N)) and for each query O(B - A) function calls will be made. So the overall time complexity will be O(Q * (B - A) * sqrt(B)). 

Space Complexity

O(1)

 

We are not using any extra space.

Code Solution
(100% EXP penalty)
NFACTOR
Full screen
Console