Էյլերի տոտիենտ ֆունկցիա
Տրված է թիվ
n. Ձեզ խնդրում են հաշվարկել Էյլերի տոտիենտ ֆունկցիայի արդյունքը։Էյլերի տոտիենտ ֆունկցիան հաշվում է 1-ից մինչև
n այն ամբողջ թվերի քանակը, որոնք հարաբերականորեն պարզ են n-ի հետ։ Այսինքն՝ բոլոր այն թվերը, որոնց ամենամեծ ընդհանուր բաժանարարը n-ի հետ հավասար է 1-ի:
Մուտք
Մուտքի միակ տողում տրված է մեկ ամբողջ թիվ
n (1 ≤ n ≤ ):Ելք
Ծրագիրը պետք է տպի
n-ի համար Էյլերի տոտիենտ ֆունկցիայի արդյունքը:Օրինակներ
Մուտք | Ելք |
20 | 8 |
9 | 6 |
Բացատրություն
- 20 → 1, 3, 7, 9, 11, 13, 17, 19
- 9 → 1, 2, 4, 5, 7
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB