1908 - Fractii Ired

Cerinţa

Dându-se şirul de fracţii 1/N, 2/N, 3/N, ...,N/N, să se afle câte fracţii sunt ireductibile.

Date de intrare

Programul citește de la tastatură numărul N.

Date de ieşire

Programul va afișa pe ecran numărul de fracţii ireductibile.

Restricții și precizări

• 1 ≤ n ≤ 2.000.000.022

Exemplu

Intrare

4

Ieșire

2

Explicație

Fracţiile sunt 1/4, 3/4.

Rezolvare

def validare_date(n):
    if not isinstance(n, int) or n < 1:
        return False
    return True

if __name__ == '__main__':
    n = int(input("Introduceti numarul: "))
    if validare_date(n):
        nr = n

        d = 2
        while n > 1:
            if n % d == 0:
                nr //= d
                nr *= d - 1
                while n % d == 0:
                    n //= d
            if d == 2:
                d = 3
            else:
                d += 2
            if d * d > n:
                d = n

        print(nr)
        print("\nDatele de intrare corespund restricțiilor impuse.\n")
    else:
        print("Datele de intrare nu corespund restricțiilor impuse.")

Explicație rezolvare

Codul Python calculează funcția Euler Totient pentru un număr natural introdus de utilizator. În timpul procesului de calcul, se parcurg divizorii primi distincti ai numărului și se aplică o formulă specifică pentru a obține valoarea funcției. Codul include, de asemenea, o verificare a datelor de intrare pentru a asigura validitatea acestora.