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

<syntaxhighlight lang="python" line> def validare_date(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 validare_date(n, arr):
       print("\nDatele de intrare corespund restrictiilor impuse.\n")
   else:
       print("Datele de intrare nu corespund restrictiilor impuse.")

   C = 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:
           C += 1

   print(C)

</syntaxhighlight>

Explicație rezolvare

În acest program, se dă un număr întreg n și un șir de n numere întregi arr. Scopul programului este de a găsi numărul de numere din șirul arr care au exact patru divizori.

Pentru a rezolva această problemă, se parcurge fiecare element din șirul arr. Pentru fiecare element x se calculează numărul de divizori folosind un algoritm care împarte numărul la toți divizorii săi, numărând fiecare divizor de câte ori apare. Dacă numărul total de divizori este patru, atunci elementul este adăugat la numărul total de numere cu patru divizori găsite până acum.

Pentru a verifica dacă datele de intrare sunt valide, se folosește o funcție numită validare_date care verifică dacă numărul n și toate elementele din arr sunt în limitele specificate. Dacă datele de intrare sunt invalide, programul se oprește și afișează un mesaj de eroare. În caz contrar, programul continuă și afișează un mesaj de confirmare.