Chambre en désordre#12212

Chambre en désordre (Corrigé)

Auteur du problème:	De3b0o
Préparé par:	De3b0o
Édité par:	Hasan Saleh (MathModel)

Solution

Remarquez que nous ne pouvons pas utiliser le côté $1$ , cela signifie que nous avons besoin de deux entiers $(a, b \geq 2)$ (a,b \ge 2) tels que $a \cdot b = n$ a \cdot b=n. Il y a deux cas, si $n$ est premier alors $n$ est impair et $n + 1$ n+1 est pair, ce qui implique que $n + 1$ n+1 est composite et donc $n + 1$ n+1 est la réponse, sinon $n$ lui-même est composite donc c'est une réponse valide.

La mise en œuvre suivante est $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 mise en œuvre suivante est $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

Complexité $O (n)$ ou $O (n)$ \mathcal{O}(\sqrt{n}) les deux passent.