Messy Room#12212

Messy Room (Editorial)

Problem Author:	De3b0o
Prepared by:	De3b0o
Edited by:	Hasan Saleh (MathModel)

Solution

Notice we cannot use the side $1$ , that means that we need some two integers $(a, b \geq 2)$ (a,b \ge 2) so that $a \cdot b = n$ a \cdot b=n , There are two cases , if $n$ is prime then $n$ is odd and $n + 1$ n+1 is even which follows that $n + 1$ n+1 is composite and thus $n + 1$ n+1 is the answer , otherwise $n$ itself is composite so it's a valid answer.

The following is $O (n)$ implementation

def solve():
    n=int(input())
    for i in range(2,n):
        if(n%i==0):
            print(n)
            return
    print(n+1)
 
for _ in range(int(input())):
    solve()

Python

The following is $O (n)$ \mathcal{O}(\sqrt{n}) implementation

from math import *
def solve():
    n=int(input())
    for i in range(2,int(sqrt(n))+1):
        if(n%i==0):
            print(n)
            return
    print(n+1)
 
for _ in range(int(input())):
    solve()

Python

Complexity $O (n)$ or $O (n)$ \mathcal{O}(\sqrt{n}) both passes.