Hello
I am solving this question from hackearth…
My logic is brute force…
First i have calculated all the prime number under n…
Now i have iterated to every index… and for every index i have calculated the all the possible prime array and updated the answer…
But it is showing wrong answer for some test cases…
Please see this…
https://www.hackerearth.com/submission/51480773/
Thanks…
Hey @ashishnnnnn i can’t see your code as i don’t have account on hackerearth. Though the intuition to solve this is:
to calculate all prime numbers till 5000 as of value of N using sieve of eratosthenes which won’t be more then 700 prime values(to be precise 668)
Then iterate from 1 to N, and store
score[i] =score[i-1]+points
Now run a for loop from 668 to 0
and wherever you find prime[i]<=n
break the for loop and hold that value of prime[i]
Now again run a for loop j, from 0 to n-holded value(prime[i])
and get maximum of score[hold+j]-score[j] for each value of J. That will be your answer. This will surely make your answer get accepted 
Hi…
I have done the same way…
https://www.hackerearth.com/submission/51519430/
Even now it is showing wrong answer…
You can take reference from here and find where were you mistaken
I have submitted that code… also… It is avilable on github…
Thant code is also showing wrong answer…
The logic of this code seems to be correct. Let me check the side cases and will let you know what is causing wrong answer. Cause the logic seems to be correct. Though would request you to also try on your own if you would find it then it would be better too.
Yaa… i am trying this from my side…
This question will be solved using dp too are you trying with that intuition or not? also to make things optimize make sieve outside main function and store all prime numbers in vector to avoid TLE. IF you aren’t able to do it let me know i would provide you with a solution. Also if you aren’t able to get dp approach you can read this editorial Link.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.
Hii…
I have tried to understand the logic of the link which you have provided…
But i couldn’t understand it properly…
I couldn’t undertsnd why they have used prefix sum//
What is the logic in if statement and how they are updating dp array…