WA in PRETNUM

general
, , , ,
1

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
2

http://www.codechef.com/viewsolution/2957626

3

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.

4

CodeChef: Practical coding for everyone. Can somebody plz tell me why this is giving wrong answer. Thanks in advance.

2 Likes
5

Here is my code: CodeChef: Practical coding for everyone
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…

6

Somebody please post the best algorithm for this question

7

@jamesbond007

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

1 Like
8

@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
9 
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.
10

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

11

please provide the code link

1 Like
12

link is given below.

13

I ran your solution : nNJIpj - Online C Compiler & Debugging Tool - Ideone.com

1

10 100

Answer : 26

your program gives : 23

Test case :

1

999999000000 1000000000000

Answer : 36400

Your program : TLE

1 Like
14

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

15

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]