Contest Link: http://www.codechef.com/CDSM2014
Problem Link: http://www.codechef.com/problems/CHFFIELD/
Author and Editorialist: Prateek Kumar
PREREQUISITES:
Basic Maths
PROBLEM:
You have to take the two dimensions of the rectangular field as input. The dimension that is a prime number is to be reduced to the closest non prime number. If the dimension can not be reduced to a non prime, then reduce it to 1. After this calculate the area of the resultant field. You have to do this for a number of test cases.
EXPLANATION:
The problem was simple, use the following algorithm to solve it:
- Take t as input
- For i=1 to t:
-
Take L and B as input<BR> -
If L<=3 then L=1<Br> -
If B<=3 then B=1<BR> -
If L>3 and Check_prime(L) is true then L=L-1<BR> -
If B>3 and Check_prime(B) is true then B=B-1<BR> - ans=L*B
- print ans
Check_prime(n)
Check if the number is divisible by any number till sqrt(n)
If divisible, then composite
Else prime
AUTHOR’S SOLUTIONS:
http://www.codechef.com/viewsolution/5441213
( The author’s solution uses a different method for prime checking, it uses prime generation)