How many ways can you think of , for writing a program that gives Euler's Totient function ?
Here are 2 that use 2 different definitions of the phi function.
\(\mathbf{1.}\) This program uses the basic definition of \(\phi(n)\) , which is
\(\phi(n)\) is the number of natural numbers less than \(n\), which are coprime to \(n\)
1 2 3 4 5 6 7 8 

Now as we took \(\text{gcd}(n,i)=1\) ,
we actually took them coprime, counting all of them and getting them in the list li
.
We print len(li)
which is length of the list, the number of natural numbers less than \(n\), which are coprime to \(n\).
\(\mathbf{2.}\) This program uses a formula by using primes,
For a natural number \(n\) , we can define \(\phi(n)\) as \[\phi(n) = n\times \prod _{p\mid n} \Bigl(1\frac{1}{p}\Bigr) \]
or in other words, if \(n = p_1^{a_1}p_2^{a_2} ... p_n^{a_n}\), then \(\phi(n) = n \Bigl(1\frac{1}{p_1}\Bigr)\Bigl(1\frac{1}{p_2}\Bigr)....\Bigl(1\frac{1}{p_n}\Bigr)\)
1 2 3 4 5 6 7 8 9 10 

Hence for every prime number \(p\) dividing \(n\), the program transforms \(n\rightarrow n  \frac{n}{p}\) , at the end resulting into the value \(\phi(n)\)
Anyone knowing any other method is welcome to post it :)
Comments
Sort by:
Top NewestHi aditya raut I am preparing for inmo this year what tips can you give ma
Log in to reply
Wow! Still no comments ? Pls wait till the 4th , I'll post a Java solution then :)
Log in to reply