If n is the numerator and d the denominator of a fraction, that fraction is defined a (reduced) proper fraction if and only if GCD(n,d)==1.

For example `5/16` is a proper fraction, while `6/16` is not, as both 6 and 16 are divisible by 2, thus the fraction can be reduced to `3/8`.

Now, if you consider a given number d, how many proper fractions can be built using d as a denominator?

For example, let's assume that d is 15: you can build a total of 8 different proper fractions between 0 and 1 with it: 1/15, 2/15, 4/15, 7/15, 8/15, 11/15, 13/15 and 14/15.

You are to build a function that computes how many proper fractions you can build with a given denominator:
```python
proper_fractions(1)==0
proper_fractions(2)==1
proper_fractions(5)==4
proper_fractions(15)==8
proper_fractions(25)==20
```

Be ready to handle big numbers.

Edit: to be extra precise, the term should be "reduced" fractions, thanks to [girianshiido](http://www.codewars.com/users/girianshiido) for pointing this out and sorry for the use of an improper word :)

Difficulty: interview

Starter code:

def proper_fractions(n):
	

Solutions:
def proper_fractions(n):
    phi = n > 1 and n
    for p in range(2, int(n ** .5) + 1):
        if not n % p:
            phi -= phi // p
            while not n % p:
                n //= p
    if n > 1: phi -= phi // n
    return phi

def proper_fractions(n):
    #find all prime factors (without repetitions) of n
    factors=set()
    i=2
    input=n
    while i*i<=input:
        if input%i==0:
            factors.add(i)
            input=input//i
        else:
            i=i+1
    factors.add(input)
    #use Euler totient formula to find the amount of numbers coprime to n that are smaller than n
    result=n
    for j in factors:
        result=result*(1-(1/j))
    return int(result)
            


def euler(n):
    res = 1.0*n
    p = 2
    while p*p <= n:
        if n%p == 0:
            while n%p == 0:
                n = n/p
            res *= (1.0 - (1.0/p) )
        p += 1
    
    if n > 1:
        res *= (1.0 - (1.0/n) )
    
    return int(res)

def proper_fractions(d):
    if d == 1:
        return 0
    return euler(d)

def proper_fractions(n):
    phi = n > 1 and n
    for p in range(2, int(n ** 0.5) + 1):
        if not n % p:
            phi -= phi // p
            while not n % p:
                n //= p
    if n > 1: phi -= phi // n
    return phi

from fractions import Fraction

# Euler's totient function
# Prime factors search can be easily optimize but it's already really fast anyway
def proper_fractions(n):
    res = Fraction(n)
    for i in range(2, int(n**0.5)+1):
        if n%i: continue
        while not n%i: n //= i
        res *= Fraction(i-1, i)
        if n == 1: break
    else: res *= Fraction(n-1, n)
    return res

def proper_fractions(n):
    if n<3: return n-1
    s,t,i =[],1,2
    while True:
        while n%i==0:t,s,n= t*(i if i in s else i-1),s+[i],n//i
        if i*i > n:return t*(n-1) if n>1 else t
        i+=1

import math;

def Factor(n):
    a, d = [], 2;
    while d * d <= n:
        if n % d == 0:
            a.append(d);
            n //= d;
        else:
           d += 1;
    if n > 1:
       a.append(n);
    return a;

def proper_fractions(n):
    if(n == 1):
        return 0;
    used, k = [], 1;
    for i in Factor(n):
        if(i not in used):
            used.append(i);
            k *= math.pow(i, Factor(n).count(i)) - math.pow(i, Factor(n).count(i) - 1);
    return k;

def unique_prime_factors(n): # Generate only one instance of each prime factor, save time ^_^
    i = 2
    factors = set()
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.add(i)
    if n > 1:
        factors.add(n)
    return factors

def proper_fractions(n):
    if n == 1:
        return 0
    output = n
    for p in unique_prime_factors(n): # We can now use Euler's totient function to solve directly!
        output //= p
        output *= (p-1)
    return output

import math
def proper_fractions(n) : 
    divisors,final,unique,i  = [],[],[],1
    while i <= math.sqrt(n):          
        if (n % i == 0) : 
            if (n / i == i) :divisors.append(i)                 
            else :divisors.extend([i , n/i])                
        i = i + 1
    divisors.sort()
    if len(divisors)<=2:return n-1
    divisors.pop(0),divisors.pop()    
    for num,item in enumerate(divisors):
        for x in divisors[0:num]:
            if not(item%x):break
        else:unique.append(item)

    for num,item in enumerate(unique):
        cache = n/item
        for x in unique[0:num]:
            cache = cache-(cache/x)
        final.append(cache)
    return(n-sum(final))

def proper_fractions(n):
    if n == 1: return 0
    res = n
    i = 2
    while i * i <= n:
        if n % i == 0:
            while n % i == 0:
                n /= i
            res -= res / i
        i += 1
    if n > 1:
        res -= res / n
    return int(res)