How can this solution get AC when it fails on

4

27 16 12 13

Which shows that in test cases, all odd values except 1 are primes. I too was wondered when my undeterministic prime test passed with 10 iterations.

Even i doubt if input goes upto 10^14 or not

https://www.codechef.com/viewsolution/27634356

This one too. A primality check of O(sqrtN) passes the test cases, even though according to the constraints itâ€™s overall TC should be around O(10^12)

@raunaqroxx @nishant403 I can assure you there were many primes more than 10^12 but not in the range of 10^14. That was an issue during test generation. Itâ€™s true the test cases were a bit weak. We are sorry for the inconvenience.

@aman_robotics This is because your code checks for numbers more than 10^7 but doesnot print any answers. Now the initial first one or two test cases donot contain such large numbers and hence you get WA verdict on those, and as you code gets a WA the bigger test cases are not used for judging. You can take my word when I say that there were indeed large primes of the order of 10^12. But in general the test cases were weak. SO this problem was solvable by Root(N) primality test.

I believe you, but the essence of the question is destroyed if you let O(n*sqrt(n)) solutions get accepted. Can you explain how the solution which is mentioned by @pritishn got accepted? It does not even check the primality of the number?

@raunaqroxx @aman_robotics Please help me with the above questionâ€¦

Almost same question asked in hackerearth oct circuits ( named count integers) and yesterday i tried the same approach

called miller rabin â€” Solution 1

I got TLE

Today i use naive approach and called the isprime function(Root(n)/6) complexity and i got tle

Solution 2

Now i saw some of solution instead of calling that function they write fnction defination

in the main body , so instead of calling isprime function again i wrote the whole function defination in the main body now i got either TLE or WA â€¦please help

here is Solution 3

Now one more thing , lets suppose the question have very good test case with same constraint or let A[i]<=10^18 then how can this question will be solved efficiently.

Please see my all above three solution , and suggest what i do so i get AC verdict and another thing which i mention.

I solved that question in October Circuits, you donâ€™t need anything other than the Sieve of EratosThenes, I made a bool array of 10^8 and it worked fine for me. You have to be careful that you have to make it a global array.

My submission - https://www.hackerearth.com/challenges/competitive/october-circuits-19/algorithm/fact-count-a6300182/submission/32762725/

And someone suggested me Miller Rabin for constraints like these. I didnâ€™t try it during the contest since I had a doubt whether a probabilistic method will give the right answer everytime or not.

yeah bro actually i always use long long int a[10^8] i got seg error or memory error , so i use miller rabin on hackerearth but when i saw editorial then i know that if i make 10^8 size vector of bool which takes 10^8 byte memory instead of 4*10^8 byte memory, but how the above solutions not work please help na.

Okay so, in your solutions the one using Miller Rabin, I suppose you should increase the value to k from 3 to something which is the maximum possible as it will increase the probability of checking the primality, so I think a k of 100 might work, and in the other solutions as they check till sqrt(a[i]) they will give TLE as the Time complexity becomes O(10^12) approximately.

These are my observations, I donâ€™t know whether I am absolutely correct or not.

you can use linear seive to find all primes upto 10^8 in count integer problem of hackerearth oct circuits. It gives all prime numbers upto N in O(N). I got that accepted using linear sieve.

I have made too many submissions to understand why some code passes and some failsâ€¦ here are my conclusions :

- every number in input is bounded by 10^12.
- certainly there are primes in the input greater than 10^11.
- all composites in the input are less than 100.
- there are no odd composite numbers in the input. (the biggest mistake).
- O(N*sqrt(mx)) solution will not pass. Reason why the mentioned submission passes is because it uses int as parameter of function, so it doesnâ€™t turn out to be TLE, I donâ€™t understand how it managed to get AC.
- Miller Rabin test (non deterministic) passes with 3 iterations. but surely it could have been failed.

I solved it using Miller Rabin Test ( non deterministic) , it gave TLE most of the time ,but after some submissions I found the no. iterations to be 3 , which passes . Here is my submission : https://www.hackerearth.com/challenges/competitive/october-circuits-19/algorithm/fact-count-a6300182/submission/32961691/

yeah exactly same i did , put k = 3 in miller rabin , but here i want solution for above q. and i asked why my solution fails (not the hackerearth q.) , so plz help!

See my last comment in this post.