This being my second Kickstart round ever, my 4th month into Competitive Programming (without any prior knowledge), and me being grey, I was proud of myself when I got an approach to Problem C, like within 20 seconds after I read it. So here goes my approach (which also happens to be similar to Kickstart's official analysis for the Test Set 3). UPD : I decided to make a YouTube video fir this question (in Hindi) : So for the solution + approach mentioned below please check the video.
The Solution
- We're given a number N, and we've to find the maximum numnber X less than or equal to N, which should be the product of any two consecutive prime numbers (if that makes sense).
- The best way would be to find two consecutive primes near the square root of N.
- Let's call the required primes a1 and a2. a1 and a2 are to be assigned to floor value of sqrt(N) and to a1+1 respectively.
- This way we get two numbers not necessarily prime near sqrt(N). Now we decrement a1 until it becomes a prime number, and increment a2 until it becomes a prime number. (Note that if any of them are already primes we stop). This step is guaranteed to give us two consecutive primes around sqrt(N).
- Now that we have a1 and a2 (consecutive primes), we check that is a1*a2 > N. If No, then we output a1*a2 and we're done with the solution.
- If Yes, then we have 2 options. Either move a1 and a2 to the next prime numbers possibloe, but this would only increase the product, therefore this isn't viable. The other option would be to move a1 and a2 to the preivious prime numbers possible. This is guaranteed to give the required two consecutive primes. (We can simply do a2 = a1; while(!prime(a1))a1--;)
- And then we just simply output a1*a2 as the result.
Here goes the Code for the above explanation : Code
(Tried my best but couldn't attach code directly to the blog, my bad)
Thank You
Regards
