World's most popular travel blog for travel bloggers.

# Sieving to compute first values of totient function

, ,
Problem Detail:

What i want to do is to compute the first $n$ values of Euler's totient function effectively. As far as i know the best way to do it is to run a sieving algorithm and for each prime encountered to update current totient-value for all its multiples. My realization in Python is given below. I use two facts about totient function:

a) if $~p~$ is prime than $~\phi(n) = n-1$

b) for any prime $~p~$ and positive integers $~a,n~$ $~\phi(p^a n) = p^a n (1 - \frac{1}{p})$

My problem is termination of main loop. My code loops till $n / 2$ though i would like to stop at $\sqrt{n}$. The problem is that some numbers above $\sqrt{n}$ may have prime divisors above $\sqrt{n}$ which won't be processed with current version of algorithm if main loop is terminated before $n / 2$. I don't understand how to handle totient function values for such numbers since calculation for them wasn't finished in fact. Any ideas on these problem will be highly appreciated. Thanks in advance!

# n >= 2 def sieve(P, n):     end = n // 2 + 1     for k in range(2, end):         if (P[k] == k):             for j in range(2*k, end, k):                 P[j] -= P[j] // k  def phi(P, n):     if (n == 1):         return 1     if (P[n] == n):         return n-1     return P[n]   n = int(input()) P = [i for i in range(0,n+1)] sieve(P, n) for k in range(1, n+1):     print(repr(k) + "  " + repr(phi(P,k))) 
###### Answered By : Yuval Filmus

The complete formula for Euler's totient function is $$\varphi(n) = n\prod_{p|n} \left(1-\frac{1}{p}\right),$$ where the product goes over all prime factors of $n$. Hence you essentially need to factor $n$ in order to compute $\varphi(n)$. You can do it in any way you wish.

Computing $\varphi(n)$ is believed to be as hard as factoring $n$ (and is indeed as hard in some special cases, for example when $n$ is a product of two primes).

You can use a sieve to factor all numbers up to $n$. The idea is to go from $2$ to $n$; whenever encountering an uncircled number $p$ (the initial state), this number must be prime, and we can circle all its multiples. Moreover, we can divide these numbers by $p$, the appropriate numbers by $p^2$, and so on. At the end, the uncircled numbers are all primes, and all other numbers have been factored.

You can easily adapt this algorithm to compute the totient function directly. Every time you encounter a new prime $p$, you divide all its multiples by $(p-1)/p$. After going through all numbers up to $n$, all uncircled numbers are prime, and so their totient function is easy to compute.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/54608

3200 people like this