Düzgün Otaq (Həll təhlili)

Həll

Qeyd edək ki, $1$ tərəfini istifadə edə bilmirik, bu o deməkdir ki, a \cdot b=n olması üçün iki tam ədədə (a,b \ge 2) ehtiyacımız var. İki hal var, əgər $n$ asal ədəd olsa, onda $n$ təkdir və n+1 cütdür, bu da n+1-in tərkib hissəsi olduğunu göstərir və beləliklə, n+1 cavabdır, əks halda $n$ özü tərkib hissəsidir, buna görə də bu, etibarlı cavabdır.

Aşağıdakı $\mathcal{O}(n)$ tətbiqi

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()

Aşağıdakı \mathcal{O}(\sqrt{n}) tətbiqi

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()

Komplekslik $\mathcal{O}(n)$ və ya \mathcal{O}(\sqrt{n}) hər ikisi keçərli.