Habitación Desordenada#12212

Habitación Desordenada (Editorial)

Autor del problema:	De3b0o
Preparado por:	De3b0o
Editado por:	Hasan Saleh (MathModel)

Solución

Observe que no podemos usar el lado $1$ , lo que significa que necesitamos dos enteros $(a, b \geq 2)$ (a,b \ge 2) tales que $a \cdot b = n$ a \cdot b=n. Hay dos casos: si $n$ es primo, entonces $n$ es impar y $n + 1$ n+1 es par, lo que implica que $n + 1$ n+1 es compuesto y, por lo tanto, $n + 1$ n+1 es la respuesta; de lo contrario, $n$ en sí es compuesto, por lo que es una respuesta válida.

La siguiente es una implementación de $O (n)$

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

La siguiente es una implementación de $O (n)$ \mathcal{O}(\sqrt{n})

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

Complejidad $O (n)$ o $O (n)$ \mathcal{O}(\sqrt{n}) ambas pasan.