Funció Fi d'Euler per un flux X25130
Dos nombres enters són coprimers si el seu màxim comú divisor és 1 (mcd(a, b) = 1), és a dir, els únics divisors comuns que tenen els dos nombres són 1 i -1. Per exemple 15 i 8 són coprimers.
La funció φ (fi) d’Euler és una funció important en la teoria de nombres i utilitza el concepte de coprimer. Si n és un nombre enter positiu, llavors φ(n) es defineix com el nombre d’enters positius menors o iguals que n i que són coprimers amb n.
Per exemple:
φ(36) = 12 ja que els nombres menors o iguals a 36 i coprimers amb 36 són 12: 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31 i 35.
Fes un programa que donat flux d’enters majors que 0 acabat en 0 escrigui per cada nombre del flux el seu valor de la funció φ d’Euler.
IMPORTANT! Has d’implementar i usar una funció que donat un nombre natural retorni el valor de la funció φ per aquest nombre.
Entrada
L’entrada consisteix en un flux d’enters majors que 0 acabat en 0.
Sortida
Mostra per cada nombre del flux en una línia:
- el nombre del flux
- dos punts
- un espai
- el valor de la funció Φ per aquest nombre.
Per obtenir més detalls sobre la sortida consulta els jocs de proves públics.
Input
30 20 12 40 10 1 1010 51 23 45 26 34 36 141 0
Output
30: 8 20: 8 12: 4 40: 16 10: 4 1: 1 1010: 400 51: 32 23: 22 45: 24 26: 12 34: 16 36: 12 141: 92
Input
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 0
Output
2: 1 3: 2 5: 4 7: 6 11: 10 13: 12 17: 16 19: 18 23: 22 29: 28 31: 30 37: 36 41: 40 43: 42 47: 46 53: 52 59: 58 61: 60
Input
7732 4321 9925 2486 1263 9020 5941 8413 5238 6610 137 2020 0
Output
7732: 3864 4321: 4144 9925: 7920 2486: 1120 1263: 840 9020: 3200 5941: 5472 8413: 8188 5238: 1728 6610: 2640 137: 136 2020: 800
- Author
- Bernardino Casas
- Language
- Catalan
- Official solutions
- C++
- User solutions
- C++