Algorithm for Totient

[Kirby Urner]

Here's an algorithm for getting the totient of N I hadn't 
seen before, which came to me yesterday:

(a) get prime factors of N in list F, set totient = 1
(b) totient *= (p-1) for each first occurance of p in 
    F, totient *= p otherwise
(c) return totient

The algorithm we more usually see in text books is:

(a) get prime factors of N in list F, set totient = n
(b) totient -= totient/p for each first occurance of 
    p in F.
(c) return totient

Here're the two algorithms in Python, which include a factor 
method returning prime factors of n (code not shown -- 
assume some sieve-based algorithm that's not practical 
for n > some biggish number).

def totient1(n):
    unique = []
    totient = 1
    for p in factor(n):
        if p not in unique:
            unique.append(p)
            totient *= p-1
        else:
            totient *= p
    return totient

def totient2(n):
    unique = []
    totient = n
    for p in factor(n):
	if p not in unique:
            unique.append(p)
            totient -= totient//p # integer division
    return output

The 2nd algorithm, found in text books, is more efficient.  So 
I guess the only interesting point here is that the two algorithms
give the same result, which could be shown by algebra.  I guess
the other point is to show how easy it is to read Python, even
if it's not what you're using.

Kirby