# PROBLEM LINK:

*Author:* Satyabrat Panda

*Tester:* Pritish Priyatosh Nayak

*Editorialist:* Pritish Priyatosh Nayak

# DIFFICULTY:

Easy-Medium

# PREREQUISITES:

Maths, Number Theory

# PROBLEM:

A rectangle with positive integer side length has area X cm^2 and perimeter Y cm. You’re given the value of X + Y. Determine if a rectangle with positive area and positive integer side length is possible for this value.

# EXPLANATION:

Assume that the length of the rectangle be a and breadth b.

Let value of X + Y be c.

So,

\implies ab + 2a + 2b = c

\implies 2a + ab + 2b + 4 - 4 = c

\implies a(2 + b) + 2(b + 2) - 4 = c

\implies (a + 2)(b + 2) - 4 = c

\implies (a + 2)(b + 2) = c + 4

The problem boils down to finding two factors of c + 4, i.e , f1 and f2

such that f1 * f2 = c + 4, f1 > 2 and f2 > 2.

Such values of f1 and f2 do not exist if (c + 4) is a prime number or twice a prime number.

So, basically we can loop from 3 to \sqrt N and check if any factor exists.

Time Complexity : O(sqrt(N))