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 :)
$</code> ... <code>$</code>...<code>."> Easy Math Editor
*italics*
or_italics_
**bold**
or__bold__
paragraph 1
paragraph 2
[example link](https://brilliant.org)
> This is a quote
2 \times 3
2^{34}
a_{i1}
\frac{2}{3}
\sqrt{2}
\sum_{i=1}^3
\sin \theta
\boxed{123}
Comments
Sort by:
Top NewestWow! Still no comments ? Pls wait till the 4th , I'll post a Java solution then :)
Log in to reply
Hi aditya raut I am preparing for inmo this year what tips can you give ma
Log in to reply