PROBLEM LINK:DIFFICULTY:EASY PREREQUISITES:Prime factorization, Sieve PROBLEM:Find the number of integers in the given range which have prime number of divisors. QUICK EXPLANATION:Although 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. EXPLANATION:Approach 1: Working commented solution follows:
Approach 2: Lets take an example: 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). See tester’s solution for working code. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution will be uploaded soon asked 11 Nov '13, 23:05

We don't need to count factors of each numbers, only for perfect squares in the range, am i right? Because apart from primes (2 factors), only perfect squares can have prime number of factors since only perfect squares have odd number of factors, other numbers have even number of factors(except 2 no of factors) So we can calculate number of factors of only perfect squares and look that up to be prime between [1,200] answered 11 Nov '13, 23:25

All we need to do is to count the no of numbers that are powers of prime such that power+1 is also prime!! ;) answered 12 Nov '13, 01:12

the numbers follow a pattern... p^(q1) where both p and q are prime ..
i used sieve to figure out all the prime numbers.. and simple math to figure out how many numbers are powers of (prime1) that comes within the given range of 'l' to 'r' .. worked out well n good !! answered 12 Nov '13, 01:56
Is this what you did? 2,3,5,7,11,...............,999999999989 squares of 2,3,5,7,.......,999983 power 4 of 2,3,5,7,.......,997 power 6 of 2,3,5,7,.......,97 power 10 of 2,3,5,7,11,13 power 12 of 2,3,5,7 power 16 of 2,3,5 power 18 of 2,3 power 22 of 2,3 power 28 of 2 power 30 of 2 and power 36 of 2 This is the pattern i could guess when i was working on this question. But then i got stuck because of the space constraint in C++. It can count the rest. The problem is only with the prime numbers after 10^6. Can you help me with this?
(04 Dec '13, 23:50)
@whizcode, sorry i couldn't get to you soon .. was occupied with december challenge.! And no that wasn't what i did, i just calculated all the prime numbers in that interval using seive and then used dp to calculate powers of (prime1) in that interval, thats all the problem requires :)
(10 Dec '13, 03:38)

Hi Admin, Could you please tell me ans for 1000000 1000100 I have checked with some solutions those are giving answer as 6 but here is one accepted solution that is giving ans 5 http://www.codechef.com/viewplaintext/2977722 as we can see ans should be 6 [1000003,1000033,1000037,1000039,1000081,1000099] Thanks, answered 12 Nov '13, 23:00

Find all perfect squares and prime numbers in the range [l,r]. Check if square root of a perfect square has exactly one prime divisor( is of the form prime^(k) ), because product of two numbers can never be prime. Then original number is prime^(2k) Number of divisors of prime^(2k) = 2k+1. Then using sieve check if 2k+1 is prime. If prime add 1 to answer. Also add number of prime numbers between [l,r] to the answer. my solution answered 17 Jun '16, 21:12

CAN ANYONE TELL WHATS WRONG WITH MY CODE http://www.codechef.com/viewsolution/2975377 answered 12 Nov '13, 20:26
Run time error for large inputs
(12 Nov '13, 21:36)

I didn't get the part where you say "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) . Also I think it should be the ((prime > 10^6) + 1) in the end,right ? answered 08 Jun '16, 14:46

Any number from the range [1,10^12]. Will have following properties:
It helped me in finding all primes in the range [l,r] answered 17 Jun '16, 21:50

The no. in the range[l,r] let us say x should be a power of a single prime no. i.e its prime factorization should be of the form x = p^q where q + 1 is a prime. The reason is that total no. of divisors of a no. with prime factorization (p1)^q1 * (p2)^q2...... (pn)^qn will have total divisors = (q1 + 1)*(q2 + 1)....(qn + 1). For total divisors of the form stated above to be prime. n should be 1. Since if its greater than 1 then no. of divisors will be composite. Now n being 1, q1 + 1 should be prime! answered 13 Feb, 10:55
