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(vector , n):

   if not 2 <= n <= 1000000:
       print("Datele nu sunt conform restricțiilor impuse.")
       return False
   for x in vector:
       if x > 100000000:
           print("Datele nu sunt conform restricțiilor impuse.")
           return False
   print("Datele sunt corecte.")
   return True
       

if __name__ == '__main__':

   n = int(input())
   vector = list(map(int, input().split()))
   if conform_restrictiilor(vector , n) is True:
       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.

Funcția conform_restrictiilor(vector , n) primește două argumente, un vector de numere întregi și un număr întreg n. Mai întâi, funcția verifică dacă n este între 2 și 1.000.000, iar dacă nu, afișează un mesaj de eroare și returnează False. Apoi, pentru fiecare element din vector, funcția verifică dacă este mai mic sau egal cu 100.000.000. Dacă se găsește un element care depășește această limită, funcția afișează un mesaj de eroare și returnează False.

Dacă toate verificările sunt trecute cu succes, funcția afișează un mesaj de confirmare și returnează True.

În programul principal, citim numărul n și cele n numere naturale de la tastatură, stocate în lista numere. Se apeleaza apoi functia conform_restrictiilor(vector , n) iar daca se returneaza True, se continua. 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.