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: EASY
Tags: Mathematics

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 ** 0.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():
	yield from PRIMES
	n = PRIMES[-1]
	limit = int(n ** 0.5)
	check = limit * limit
	while True:
		n += 2
		if check < n:
			limit += 1
			check = limit * limit
		for p in PRIMES:
			if n % p == 0:
				break
			if p > limit:
				PRIMES.append(n)
				yield n
				break

def prime_factors(n):
	if n < 2:
		return []
	factors = []
	for p in primes():
		if n % p == 0:
			factors.append(p)
			while n % p == 0:
				n //= p
		elif p * p > n:
			factors.append(n)
			n = 1
		if n <= 1:
			break
	return factors

def totient(n):
	if not isinstance(n, int) or n < 1:
		return 0
	factors = prime_factors(n)
	if not factors:
		return 1
	if factors[0] == n:
		return n - 1
	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 ** 0.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