Has anyone got WA for PRETNUM in spite of checking all scenarios. I tested all crucial cases and got them right. But when I am submitting it, I got WA. Can anyone tell me some important test cases?

1 Like

now that that contest is over, you could just take someone code and generate test cases

please provide the code link

1 Like


Here is the link to the code…http://www.codechef.com/viewplaintext/2974261. I’ve tested it against all the cases given in comments. But no help.

link is given below.

http://www.codechef.com/viewsolution/2976935. Can somebody plz tell me why this is giving wrong answer. Thanks in advance.


I ran your solution : http://ideone.com/nNJIpj


10 100

Answer : 26

your program gives : 23

Test case :


999999000000 1000000000000

Answer : 36400

Your program : TLE

1 Like

Here is my code: http://www.codechef.com/viewsolution/2978347
I constantly get runtime error for l=999970000000 and above values…
Can someone please tell me what the problem is?
I had spent days trying to figure out the bug but just cant seem to find it…

Someone please tell the Error in this code. Can’t figure out even after trying all the cases correctly.

Somebody please post the best algorithm for this question


Don’t check for all the numbers in the range, only for the prefect squares in the range

1 Like

@jamesbond007 There are 2 parts to this question:

  1. Finding all the prime numbers in the range [L,R]. This will have to be done using sieve of erasthones.For everybody struggling with this part , i would suggest you have a look at this question PRIMED. We have to include these numbers because all prime numbers have 2 factors and hence should be included

2)finding all numbers of the form p1^(p2-1) in the range [L,R] where p1 and p2 are prime numbers. We have to include these numbers because the number of divisors of such numbers are ( p2 -1 ) +1 = p2 which is a prime and satisfies the condition given in the question. this can be tested by using brute force.

1 Like

Or for the second part, we can just find no of factors of prefect squares between [L,R] because only perfect squares have odd number of factors and then we can check it to be prime between [3,169]

Here is how i approached it.
1. All the primes have exactly 2 divisors (2 is the only even prime.) and so they contribute to the solution (use segmented sieve)
2. Consider only perfect squares ( see if (floor(sqrt(n))^2 == n ) ->  Divisors come in pairs. I.e for every i that divides n we have n/i which also divides n. So all the numbers except perfect squares have even number of divisors (which will be an even number greater than 2) so they can be safely ignored. Perfect squares have odd number of divisors because when i = sqrt(n) , both i and n/i are same. You just have to see if this odd number of divisors is a prime.