Sieving to compute first values of totient function

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)))


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.

• That's exactly what i tried to implement! But i still don't understand the following situation. If n = 20 then we sieve up to 4. On the place of number 14 we will have 7 since only its prime divisor 2 was encountered. But the correct answer is 6. Could you explain please how you handle such situation?
– Igor
Mar 18, 2016 at 0:16
• Sorry, my mistake. You just have to go all the way up to $n$. (Or, put differently, to also process all primes larger than $\sqrt{n}$.) Mar 18, 2016 at 0:20
• So my original approach to sieve up to n / 2 is good enough?
– Igor
Mar 18, 2016 at 0:21
• OK. You answered my question. Thanks :)
– Igor
Mar 18, 2016 at 0:21