NFACTOR

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”.

Since for each query, 1 <= N <= 10 we can store the integers in the range [1, 100000] which are having unique prime factors less than or equal to 10.

Algorithm:

1. Create an array/list “bin” of size 11 where the i-th index stores the number of integers in the range [1, 10000] having ‘i’ unique prime factors.
2. Now, start iterating using a variable ‘i’ such that 1 <= ‘i’ <= 10000
   • Get the count of unique prime factors using the primeFactors() function as described in Approach 1.
   • If the count is between 1 and 10 then add the current element in its correct position in “bin”.

Now, for answering the query we will iterate through the list of integers having ‘n’ number unique prime factors and count the integers in the range [A, B].

Let us try to optimize the primeFactors() function. The basic idea is to store the Smallest Prime Factor(SPF) for every number in the range [1, 10000]. And then to calculate the prime factorization of the given number by dividing the given number recursively with its smallest prime factor till it becomes 1.

Algorithm:

1. Create an array/list “spf” whose i-th element stores the smallest prime factor of ‘i’. And mark the smallest prime factor of each element to itself.
2. Now, for calculating the smallest prime factor for each number in the range [1, 10000]. Start iterating using a variable ‘i’ such that 2 <= ‘i’ <= 10000.
   • If spf[i] == 'i' which means the current element is a prime number. We will update the “spf” array/list for each number having the current element ‘i’ as the smallest prime factor.
   • Start iterating using a variable ‘j’ such that i * i <= j <= 10000. And at each iteration, we’ll increment the ‘j’ by ‘i’ because we are in search of integers that are multiple of ‘i’.
     • Now, if spf[j] == 'j' then update “spf” as spf[j] = ‘i’.

Now let us implement the primeFactors(int n) function:

1. Create a variable “count” to store the count of unique prime factors of a given integer ‘n’.
2. Loop until ‘n’ is not equal to 1
   • Store the smallest prime factor of ‘n’ in a variable ‘x’.
   • Divide ‘n’ until it is divisible by ‘x’.
   • Update “count” as count = count + 1
3. Return “count”

Since for each query, 1 <= N <= 10 we can store the integers in the range [1, 10000] which are having unique prime factors less than or equal to 10.

Algorithm:

1. Create an array/list “bin” of size 11 where the i-th index stores the number of integers in the range [1, 10000] having exactly ‘i’ unique prime factors.
2. Now, start iterating using a variable ‘i’ such that 1 <= ‘i’ <= 10000.
   • Get the count of prime factors using the primeFactors() function as described in above.
   • If the count is between 1 and 10 then add the current element in its correct position in “bin”.

Since each array/list of “bin” is sorted in non-decreasing order, for answering the query we can do a binary search to find the number of integers in the range [A, B] from the list of integers having ‘n’ number of unique prime factors.