In number theory, Euler's totient is an arithmetic function, introduced in 1763 by Euler, that counts the positive integers less than or equal to `n` that are relatively prime to `n`. Thus, if `n` is a positive integer, then `φ(n)`, notation introduced by Gauss in 1801, is the number of positive integers `k ≤ n` for which `gcd(n, k) = 1`.  
The totient function is important in number theory, mainly because it gives the order of the multiplicative group of integers modulo `n`. The totient function also plays a key role in the definition of the RSA encryption system.

For example `let n = 9`.  
Then `gcd(9, 3) = gcd(9, 6) = 3` and `gcd(9, 9) = 9`.  
The other six numbers in the range `1 ≤ k ≤ 9` i.e. `1, 2, 4, 5, 7, 8` are relatively prime to `9`.  
Therefore, `φ(9) = 6`.  
As another example, `φ(1) = 1` since `gcd(1, 1) = 1`.

There are generally two approaches to this function:

* Iteratively counting the numbers `k ≤ n` such that `gcd(n,k) = 1`.

* Using the Euler product formula.  
  This is an explicit formula for calculating `φ(n)` depending on the prime divisor of `n`:  
  `φ(n) = n * Product (1 - 1/p)` where the product is taken over the primes `p ≤ n` that divide `n`.  
  For example: `φ(36) = 36 * (1 - 1/2) * (1 - 1/3) = 36 * 1/2 * 2/3 = 12`.  
  This second method seems more complex and not likely to be faster, but in practice we will often look for `φ(n)` with `n` prime. It correctly gives `φ(n) = n - 1` if `n` is prime. 

You have to code the Euler totient function, that takes an integer `1 ≤ n` as input and returns `φ(n)`.

```if:javascript
You do have to check if `n` is a number, is an integer and that `1 ≤ n`; if that is not the case, the function should return `0`.
```

```if:python
You do have to check if `n` is a number, is an integer and that `1 ≤ n`; if that is not the case, the function should return `0`.
```

```if:racket
`n` is always a positive integer.
```

Input range: `1 ≤ n ≤ 1e10`

Difficulty: introductory

Starter code:

def totient(n):
	

Solutions:
def totient(n):
    if not isinstance(n,int) or n<1: return 0
    
    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

PRIMES = [2, 3, 5, 7, 11, 13, 17, 19]

def primes():
    """Yields 'all' prime numbers"""
    yield from PRIMES
    
    # Last known prime
    n = PRIMES[-1]
    # Approx limit of primes that can be factors
    limit = int(n ** 0.5)
    check = limit * limit

    while True:
        # Next prime candidate for testing
        n += 2
        # Maintain limit
        if check < n:
            limit += 1
            check = limit * limit
        
        # Using Fundamental Theorem of Arithemtic we only need to check primes are factors to determine if composite
        for p in PRIMES:
            if n % p == 0:
                # n has a prime factor, so it is not prime
                break
            if p > limit:
                # No further primes can be a factor as the counterpart n/p would have already been found.
                # So n must be prime
                PRIMES.append(n)
                yield n
                break


def prime_factors(n):
    """Returns the prime factors of n"""
    if n < 2:
        return []
    factors = []
    for p in primes():
        if n % p == 0:
            # Found a factor
            factors.append(p)
            while n % p == 0:
                n //= p
        elif p * p > n:
            # No need for more tests, the residual value must be prime
            factors.append(n)
            n = 1
        
        if n <= 1:
            # Found all prime factors
            break
    return factors

def totient(n):
    if not isinstance(n, int) or n < 1:
        return 0
    
    factors = prime_factors(n)
    # print(f'Prime factors of {n}: {factors}')
    if not factors:
        # Only gcd(1, 1) == 1
        return 1
    
    if factors[0] == n:
        # n is prime, so all gcd([1..n - 1], n) == 1
        return n - 1

    # Apply Euler's product formula to calculate totient: n * prod((f - 1) / f)
    for f in factors:
        n //= f
        n *= f - 1
    return n


def totient(n):
    try:
        assert isinstance(n, int) and n > 0
        phi = n
        if not n % 2:
            phi -= phi // 2
            while not n % 2: n //= 2
        for p in range(3, int(n ** .5) + 1, 2):
            if not n % p:
                phi -= phi // p
                while not n % p: n //= p
        if n > 1: phi -= phi // n
        return phi
    except: return 0

from itertools import count, chain
from fractions import Fraction
from functools import reduce
from operator import mul

def primes(n):
    for x in chain([2], count(3, 2)):
        if n == 1: return
        if x**2 > n:
            yield Fraction(n-1, n)
            return
        elif not n % x: 
            yield Fraction(x-1, x)
            while not n % x: n //= x

def totient(n):
    return reduce(mul, primes(n), n) if type(n) == int and n >= 1 else 0


def totient(n):
    if not isinstance(n, int) or n<1:
        return 0
    factor=prime_factorization(n)
    up=1
    down=1
    for i in factor:
        up*=(i-1)
        down*=i
    return n*up//down
def prime_factorization(n):
    res=set()
    while n>1 and n%2==0:
        res.add(2)
        n//=2
    while n>1 and n%3==0:
        res.add(3)
        n//=3
    factor=5
    while factor*factor<=n:
        if n%factor==0:
            res.add(factor)
            n//=factor
            factor=5
        else:
            factor+=1
    if n>1:
        res.add(n)
    return res

def prod(a, s=1):
    for p in a: s *= p
    return s

def prime_factors(n):
    for d in range(2, int(n ** 0.5) + 1):
        while n % d == 0:
            yield d
            n //= d
    if n > 1:
        yield n

def totient(n):
    if type(n) is not int or n < 0: return 0
    return round(n * prod(1 - 1 / p for p in set(prime_factors(n))))

def totient(n):
    try:
        if n <= 0 or type(n).__name__ == str or n == None:
            return 0
        result = n
        p = 2
        while p * p <= n:
            if n % p == 0:
                while n % p == 0:
                    n = n // p
                result = result * (1 - (1 / float(p)))
            p = p + 1
    
        if (n > 1):
            result = result * (1 - (1 / float(n)))
    
        return int(result)
    except Exception:
        return 0

import numbers, math
from fractions import Fraction
def primeFactors(n): 
    c = n
    p = []
    while n % 2 == 0:
        if not 2 in p: p.append(2)
        n /= 2
    for i in range(3,int(math.sqrt(n))+1,2):
        while n % i== 0:
            if not i in p: p.append(int(i))
            n /= i 
    if n!=1: p.append(int(n))
    return p or [c]

def totient(n):
    if not isinstance(n, numbers.Number) or n<1: return 0
    if n==1: return n
    res = Fraction(1,1)
    print((n, primeFactors(n)))
    for p in primeFactors(n):
        res*=Fraction(p-1, p)
    return Fraction(n,1)*res
    


def totient(n):
    if type(n) is not int or n < 0: return 0
    tot = 1
    p = 2
    while n > 1 and p * p <= n:
      k = 0
      while n > 0 and n % p == 0:
        k += 1
        n //= p
      if k > 0: tot *= p ** (k - 1) * (p - 1)
      p += 1
    if n > 1: tot *= (n - 1)
    return tot

def totient(a):
    try:
        res = max(int(a),0)
        b = a
        i = 2
        while i*i <= a:
            if a % i == 0:
                res -= res//i
                while a % i == 0:
                    a //= i
            i = i+1
        if(a>1):
            res -= res//a
        return res
    except:
        return 0