0380 - A Prim 1

Cerinţa

Se citește un număr natural și apoi n numere naturale. Să se determine câte dintre ele sunt aproape prime.

Date de intrare

Programul citește de la tastatură numărul n, și apoi n numere naturale.

Date de ieşire

Programul afișează pe ecran numărul C, reprezentând câte dintre numerele citite sunt aproape prime.

Restricții și precizări

• 1 ≤ n ≤ 100
• cele n numere citite sunt cuprinse între 1 și 1.000.000.000

Exemplu

Intrare

6

35 55 12 6 25 50

Ieșire

3

Rezolvare

def validate_data(n, arr):
    if not 1 <= n <= 10**5:
        return False
    for a in arr:
        if not 1 <= a <= 10**9:
            return False
    return True

if __name__ == '__main__':
    n = int(input())
    arr = list(map(int, input().split()))

    if validate_data(n, arr):
        print("\nDatele de intrare corespund restrictiilor impuse.\n")
    else:
        print("Datele de intrare nu corespund restrictiilor impuse.")

    cnt = 0
    for i in range(n):
        x = arr[i]
        d = 2
        cn = 1
        while x > 1:
            p = 0
            while x % d == 0:
                p += 1
                x //= d
            d += 1
            cn *= (p + 1)
            if d * d > x:
                d = x
        if cn == 4:
            cnt += 1

    print(cnt)

Explicație rezolvare

Acest program primește de la utilizator un număr n și o listă de n numere întregi și verifică dacă acestea respectă anumite restricții. Mai precis, n trebuie să fie un număr întreg între 1 și 10^5 inclusiv, iar fiecare număr din lista arr trebuie să fie un număr întreg între 1 și 10^9 inclusiv. Dacă datele de intrare sunt valide, programul afișează un mesaj de confirmare.

Apoi, programul calculează câte dintre numerele din lista arr au exact 4 divizori. Pentru a face acest lucru, se parcurg toate numerele din lista, iar pentru fiecare număr x, se calculează numărul său de divizori prin factorizarea în factori primi a lui x. Se folosește o metodă eficientă care calculează numărul de divizori al lui x ca produsul (p + 1) pentru fiecare factor prim p ridicat la puterea sa corespunzătoare în factorizarea lui x. Dacă numărul de divizori este 4, se incrementează un contor. La final, programul afișează numărul de numere din lista arr care au exact 4 divizori.