ओयलर का टोटिएंट फ़ंक्शन (Euler's totient function)
दिए गए
n के लिए, आपको ओयलर के टोटिएंट फ़ंक्शन का परिणाम निकालना है।ओयलर का टोटिएंट फ़ंक्शन 1 से
n तक उन सभी संख्याओं की गिनती करता है, जो n से परस्पर अभाज्य हैं। इसका मतलब है कि उन सभी संख्याओं का n के साथ महत्तम समापवर्तक (gcd) 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