I couldn't solve this problem , so when I looked into its editorial I got to learn about the Goldbach's conjecture . It is fascinating for me, because this has not been proven formally yet, but somebody created an interesting problem with this.
Have you encountered any such conjecture in the problem set, if Yes, please share the conjecture and the problem. And also, if you were able to solve such problem on your own, what did you do ( I mean did you follow some intuitions, or searched for some related concepts)
Thank you !!
Goldbach was also used in proof of 584D - Dima and Lisa
I was able to solve this question on my own. I initially thought this was a dp problem, so I tried to find the answer for all n<10. I came up with the values but could not make any sense of them. So I tried to use OEIS. This was also unsuccessful. Upon closer inspection I noted that for all prime number the answer would be 1. I also saw that for all even numbers less than 10 they could be expressed as the sum of 2 primes. I then googled this and came across the goldbach conjecture.
By now I had two observations
1) If n is prime ans=1
2) If n is even ans=2.
The only numbers left were odd composite number. I noticed that the difference between such number and a odd prime would be even.
After this I implemented my approach taking care of n=2.
It's worth pointing out that the conjecture is verified up to a fairly large value. I think, that in most cp problems your numbers dont go larter than that.
This is also the case for some probability checking method, like Miller-Rabin for example.