PROBLEM LINKDIFFICULTYMEDIUM PREREQUISITESPrime Factorization, Sieve PROBLEMFind the number of integers in the given range which have prime number of divisors. QUICK EXPLANATIONAlthough L and R can be as high as 10^12 but RL is <= 10^6, this allows us to iterate through the complete range and count the number of divisors of each number in the range. EXPLANATIONApproach 1: If a number N is divisible by D then either it has 2 factors(D and N/D) or it is square of D. Another thing to note is that if a number has 2 divisors x and y such that x < y, then x < sqrt(N) and y > sqrt(N). Using these 2 facts we can iterate through all the numbers in range [1, sqrt(R)] and count the number of factors for each of the number. Working commented solution follows:
Approach 2: This approach is taken by more coders. This is based on prime factorization of a number and then counting the total number of divisors. Lets take an example: Consider prime factors breakdown of 18 (2^1 * 3^2) so total number of factors are (1+1) * (2 + 1) = 6 [Factors: 1, 2, 3, 6, 9, 18]. Similarly if a number is p1^x1 * p2^x2 * p3^x3 * … then total number of factors is (x1+1) * (x2+1) * (x3+1) * … Now if we generate all primes <= 10^6 using sieve and later use them to find out how many times it goes into each number in the given range, we know the number of divisors composed of primes <= 10^6. We may have missed 1 prime number > 10^6 which might have fallen in the range as range goes as high as 10^12. But we are sure that there is only 1 such prime! So if we detect this case we can simply multiply our number of factors calculated so far by (1+1). asked 13 Oct '16, 21:54
