# WA in PRETNUM

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

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.

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

2 Likes

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…

Somebody please post the best algorithm for this question

@jamesbond007

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

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

1 Like

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

1

10 100

Test case :

1

999999000000 1000000000000