1307 - Siruri 1

Cerinţa

Se citeşte un şir X de numere naturale cu n elemente. Scrieţi un program care determină şirul Y de numere prime distincte, care figurează la puterea întâi în cel puţin o descompunere ȋn factori primi a unui număr din șirul X. Dacă niciun element al şirului X nu are un factor prim la puterea întâi, atunci se va tipări mesajul Sirul Y este vid.

Se vor scrie subprograme pentru:

• citirea unui şir de numere naturale
• tipărirea unui şir
• generarea tuturor numerelor prime mai mici sau egale decât un număr dat SAU verificarea dacă un număr este prim (ȋn funcție de modalitatea de rezolvare aleasă)
• verificarea dacă un număr figurează la puterea întâi în descompunerea unui număr dat
• construirea șirului Y

Date de intrare

Programul citește de la tastatură numărul n, iar apoi cele n elemente ale șirului X.

Date de ieşire

Programul va afișa pe ecran elementele șirului Y, ordonate crescător, separate prin câte un spațiu.

Restricții și precizări

• 1 ⩽ n ⩽ 500
• cele n numere citite vor fi mai mici decât 1000

Exemplul 1

Intrare

7

77 58 77 31

Ieșire

2 7 11 29 31

Exemplul 2

Intrare

4

64 36 100 125

Ieșire

Sirul Y este vid.

Exemplul 3

Intrare

4

25 5 125 5

Iesire

5

Rezolvare

<syntaxhighlight lang="python" line>

1. Funcția pentru a verifica dacă un număr este prim

def este_prim(n):

   if n < 2:
       return False
   for i in range(2, int(n**0.5) + 1):
       if n % i == 0:
           return False
   return True

n = int(input())

1. Citim elementele șirului

sir = list(map(int, input().split()))

1. Inițializăm un set gol pentru a stoca numerele prime unice

Y = set()

1. Parcurgem fiecare număr din șir

for x in sir:

   # Verificăm fiecare divizor al numărului
   for i in range(2, x + 1):
       # Dacă 'i' este un divizor al lui 'x', 'i' este prim și 'x' nu este divizibil cu pătratul lui 'i'
       if x % i == 0 and este_prim(i) and x % (i*i) != 0:
           # Adăugăm 'i' în setul 'Y'
           Y.add(i)

1. Verificăm dacă setul 'Y' este gol

if len(Y) == 0:

   print("Sirul Y este vid.")

else:

   # Sortăm și afișăm elementele din 'Y'
   print(' '.join(map(str, sorted(Y))))

</syntaxhighlight>