मध्यम 0 हल किए गए 0% स्वीकृति

Euler's Totient

Count the integers from 1 to n that share no common factor with n.

आप क्या सीखेंगे

  • Find the distinct prime factors of n
  • Apply φ(n) = n × Π(1 − 1/p) with integers only
  • Handle n = 1 and prime n

समस्या

अनुवाद दिखाएँ

Euler's totient function φ(n) counts the integers k with 1 ≤ k ≤ n and gcd(k, n) = 1. For example, φ(9) = 6, because 1, 2, 4, 5, 7 and 8 have no common factor with 9.

Implement eulers_totient(n).

Counting one k at a time is too slow for n up to 10^12. Use the product formula instead: φ(n) = n × (1 − 1/p) for every distinct prime p that divides n. Doing it in integers as n / p × (p − 1) avoids fractions.

Input

n: A positive integer.

Output

Return φ(n). By the definition φ(1) = 1.

सीमाएँ

1 ≤ n ≤ 10^12

उदाहरण

उदाहरण 1
इनपुट:
n = 36

अपेक्षित आउटपुट:
expected = 12
इनपुट:
long long n = 36;

अपेक्षित आउटपुट:
long long expected = 12;
इनपुट:
long n = 36;

अपेक्षित आउटपुट:
long expected = 12;

व्याख्या

36 = 2² × 3², so φ(36) = 36 × (1 − 1/2) × (1 − 1/3) = 36 × 1/2 × 2/3 = 12.

उदाहरण 2
इनपुट:
n = 13

अपेक्षित आउटपुट:
expected = 12
इनपुट:
long long n = 13;

अपेक्षित आउटपुट:
long long expected = 12;
इनपुट:
long n = 13;

अपेक्षित आउटपुट:
long expected = 12;

व्याख्या

13 is prime, so every k from 1 to 12 is coprime to it and φ(13) = 12.

कैसे हल करें

पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।

संकेत 1

Factor n by trial division up to √n.

संकेत 2

For each distinct prime p, replace the result by result / p × (p − 1); divide first so the value stays small.

संकेत 3

A leftover factor above 1 after the loop is a prime too.

अपेक्षित जटिलता

O(√n) time, O(1) extra space

संदर्भ

यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।

हर कोडर का सबसे अच्छा पास हुआ समाधान। तेज़, कम मेमोरी वाले और बेहतर रेटिंग वाले समाधान ऊपर रहते हैं।

अभी कोई पास हुआ समाधान नहीं है। इसे हल करें और पहला स्थान पाएँ।

दूसरों से सीखें

समुदाय समाधान

अभी तक कोई प्रकाशित समाधान नहीं। पहला साझा करने के लिए इस चुनौती को हल करें।