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

<syntaxhighlight lang="python" line> def validate_input(n):

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

if __name__ == '__main__':

   n = int(input("Introduceti numarul: "))
   if validate_input(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.")

</syntaxhighlight>

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.