3289 - Max Prime Intre Ele

Cerinţa

Indicatorul lui Euler, φ(n) – uneori numită funcția phi, este folosit pentru a determina câte numere mai mici decât n sunt relativ prime cu n. De exemplu, cum 1, 2, 4, 5, 7 și 8 sunt toate mai mici decât 9 și relativ prime la 9, φ(9)=6.

n Relativ prime φ(n) n/φ(n) 2 1 1 2 3 1,2 2 1.5 4 1,3 2 2 5 1,2,3,4 4 1.25 6 1,5 2 3 7 1,2,3,4,5,6 6 1.1666…. 8 1,3,5,7 4 2 9 1,2,4,5,7,8 6 1.5 10 1,3,7,9 4 2.5 Se poate vedea că n=6 produce valoarea maximă n/φ(n) pentru n ≤ 10.

Se consideră un șir de numere naturale mai mari decât 1, numere formate din cel mult 9 cifre. Să se scrie un program care determină dintre acestea numărul n pentru care raportul n/φ(n) are valoare maximă. În cazul în care sunt mai multe valori pentru care raportul n/φ(n) este maxim se va afișa prima dintre ele.

Date de intrare

Fișierul de intrare maxprimeintreele.in conține pe prima linie cel mult 10000 numere naturale din intervalul [2,999999999] separate prin spații.

Date de ieşire

Fișierul de ieșire maxprimeintreele.out va conține pe prima linie numărul k, reprezentând numărul n pentru care raportul n/φ(n) are valoare maximă.

Restricții și precizări

• numerele din fișierul de intrare sunt din intervalul [2, 999999999]

Exemplu

maxprimeintreele.in

2 3 4 5 6 7 8 9 10

maxprimeintreele.out

6

Explicație

Dintre numerele aflate în fișierul de intrare, numărul 6 are raportul n/φ(n) cu valoare maximă și anume 3.

Rezolvare

import math

def totient(nr):
    rank = nr
    if nr == 1:
        return 0
    if nr % 2 == 0:
        rank -= rank // 2
        while nr % 2 == 0:
            nr //= 2
    i = 3
    while i * i <= nr:
        if nr % i == 0:
            rank -= rank // i
            while nr % i == 0:
                nr //= i
        i += 2
    if nr > 1:
        rank -= rank // nr
    return rank


def validare_date(valoare):
    try:
        valoare_int = int(valoare)
        if valoare_int > 0:
            return valoare_int
        else:
            print("Numărul trebuie să fie pozitiv.")
    except ValueError:
        print("Intrare invalidă. Vă rugăm să introduceți un număr întreg.")


if __name__ == '__main__':
    print("Introduceți numere întregi pozitive. Pentru a opri introducerea de numere, introduceți orice altă valoare.")
    valoare_max = 0
    nr_max = 6
    while True:
        valoare = input()
        if valoare_max and not valoare:
            break
        valoare_int = validare_date(valoare)
        if not valoare_int:
            continue
        if valoare_int / totient(valoare_int) > valoare_max:
            valoare_max = valoare_int / totient(valoare_int)
            nr_max = valoare_int

    if nr_max:
        print(f"Numărul cu valoarea maximă a x/totient(x) este {nr_max}.")
        print("\nDatele de intrare corespund restricțiilor impuse.\n")
    else:
        print("Nu ați introdus niciun număr valid.")
        print("Datele de intrare nu corespund restricțiilor impuse.")

Explicație rezolvare

Programul este o implementare a funcției Euler Totient, care calculează numărul de numere întregi pozitive mai mici decât un anumit număr și care sunt prime relativ cu acel număr. Programul primește date de intrare de la utilizator, validează datele și calculează valoarea x/totient(x) pentru fiecare valoare introdusă. Programul afișează valoarea maximă a x/totient(x) și indică dacă datele de intrare introduse de utilizator au fost valide sau nu.