Problemi 015

Kërkesa

Gjeni nëse një numër i dhënë është i thjeshtë ose jo (pra nuk ka plotpjesëtues të tjerë përveç 1-shit dhe vetes).

Referenca: https://www.codechef.com/problems/PRB01

Shembull

$ cat input.txt
5
23
13
20
1000
99991

$ python3 prog.py < input.txt
yes
yes
no
no
yes

Zgjidhja 1

T = int(input())
for t in range(T):
    N = int(input())
    i = 2
    while i < N:
        if N % i == 0:
            print("no")
            break
        i += 1
    if i == N:
        print("yes")

Sqarime

Kontrollojmë me radhë numrat nga 2 në N-1, dhe nëse gjendet ndonjë që e plotpjesëton (mbetja e pjesëtimit është 0), printojmë “no” dhe ndërpresim ciklin (me break). Nëse kemi shkuar deri në fund të kontrollit pa e ndërprerë ciklin, i bie që është numër i thjeshtë, kështu që printojmë “yes”.

Zgjidhja 2

T = int(input())
for t in range(T):
    N = int(input())
    for i in range(2, N):
        if N % i == 0:
            print("no")
            break
    else:
        print("yes")

Sqarime

E njëjta llogjikë si më sipër, por e realizuar me një cikël for (në vend të while). Vini re që else-i i for-it zbatohet vetëm kur cikli shkon deri në fund (pa u ndërprerë nga break).

Zgjidhja 3

T = int(input())
for t in range(T):
    N = int(input())
    i = 2
    while i*i < N:
        if N % i == 0:
            print("no")
            break
        i += 1
    if i*i >= N:
        print("yes")

Sqarime

Mjafton që të kontrollojmë numrat nga 2 deri te rrënja katrore e N.

Zgjidhja 4

def is_prime(n):
    i = 2
    while i*i < n:
        if n % i == 0:
            return "no"
        i += 1
    return "yes"

for _ in range(int(input())):
    print(is_prime(int(input())))

Sqarime

Përdorimi i një funksioni në këtë rast e thjeshton llogjikën e programit.

Detyra

Bëni një program që gjen rrënjën katrore natyrore (të përafërt) të një numri natyror të dhënë.

Referenca: https://www.codechef.com/problems/FSQRT

Shembull

$ cat input.txt
3
10
5
10000

$ python3 prog.py < input.txt
3
2
100