3460 - FirstPrime

Sursa: - FirstPrime

---

Cerinţa

Se dau n numere naturale. Definim FP(x) cel mai mic număr prim care îl divide pe x. Aflați suma FP-urilor celor n numere.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt corecte.", iar apoi va afișa pe ecran numărul S. În caz contrar, se va afișa pe ecran: "Datele nu sunt comform restricțiilor impuse.".

Restricţii şi precizări

• 2 ≤ n ≤ 1.000.000
• cele n numere citite vor fi mai mici decât 100.000.000

Exemple

Exemplul 1

Intrare

4

2 13 9 25

Ieșire

Datele sunt corecte.

23

Exemplul 2

Intrare

5

16 7 90 19 82

Ieșire

Datele sunt corecte.

32

Exemplul 3

Intrare

2

314515341535441 412351541241

Ieșire

Datele nu sunt comform restricțiilor impuse.

Rezolvare

<syntaxhighlight lang="python" line>

1. 3460 FirstPrime

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

def fp(x):

   if x < 2:
       return 0
   for i in range(2, int(x ** 0.5) + 1):
       if x % i == 0:
           return i if este_prim(i) else 0
   return x
   
   

def conform_restrictiilor():

   n = int(input())
   vector = list(map(int, input().split()))
   if not 2 <= n <= 1000000:
       print("Datele nu sunt conform restricțiilor impuse.")
       exit()
   for x in vector:
       if x > 100000000:
           print("Datele nu sunt conform restricțiilor impuse.")
           exit()
   print("Datele sunt corecte.")
   return vector, n
       

if __name__ == '__main__':

   vector , n = conform_restrictiilor()
   suma_fp = sum(fp(x) for x in vector)
   print(suma_fp)

</syntaxhighlight>

Explicaţie cod

Funcția este_prim(n) primește un număr întreg pozitiv n și returnează True dacă n este prim și False în caz contrar. Implementarea folosește o metodă eficientă de verificare a primalității care verifică toți divizorii numărului n până la radicalul pătrat din n.

Funcția fp(x) primește un număr întreg pozitiv x și returnează cel mai mic număr prim care îl divide pe x sau 0 dacă x este mai mic decât 2 sau nu are divizori primi.

În programul principal, citim numărul n și cele n numere naturale de la tastatură, stocate în lista numere. Pentru a calcula suma FP-urilor celor n numere, iterăm prin lista numere și pentru fiecare element apelăm funcția fp(x) pentru a determina cel mai mic număr prim care îl divide pe x. Suma acestor valori este stocată în variabila suma_fp. La final, afișăm valoarea variabilei suma_fp.