fractions.py

def gcd(a, b):
    """Calculate the Greatest Common Divisor of a and b.

    Unless b==0, the result will have the same sign as b (so that when
    b is divided by it, the result comes out positive).
    """
    while b:
        a, b = b, a%b
    return a


def prime_test(n):
    if n == 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    j = 5
    while j * j <= n:
        if n % j == 0 or n % (j + 2) == 0:
            return False
        j += 6
    return True


def proper_fractions(n):
    if n == 1 or n == 2: return n - 1
    if prime_test(n):
        return n - 1
    count = 1
    for i in range(2, (n / 2) + 1):
        if gcd(n, i) == 1:
            count += 1
    return count * 2