Безладна кімната (Розбір)

Розв'язок

Зверніть увагу, що ми не можемо використовувати сторону $1$, це означає, що нам потрібні два цілі числа (a,b \ge 2) так, щоб a \cdot b=n. Є два випадки: якщо $n$ просте, то $n$ непарне, а n+1 парне, що означає, що n+1 складне, і таким чином n+1 є відповіддю; в іншому випадку, саме $n$ є складним, отже, це дійсна відповідь.

Наступна реалізація має складність $\mathcal{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()

Наступна реалізація має складність \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()

Складність $\mathcal{O}(n)$ або \mathcal{O}(\sqrt{n}) обидва проходять.