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

#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)

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.