Problem:
Euler's Phi Function For given integer n , count the totatives of n , that is, the positive integers less than or equal to n that are relatively prime to n . Input  n  An integer n (1 ≤ n ≤ 1000000000). Output The number of totatives in a line. Sample Input 1 6 Sample Output 1 2 Sample Input 2 1000000 Sample Output 2 400000

Solution (Python):
"""
https://twitter.com/kiri8128/status/1240504897419673600
https://twitter.com/kiri8128/status/1241033090773860353
"""
from collections import defaultdict
from math import gcd
from typing import Dict, Optional


def is_prime_miller_rabin(n: int) -> bool:
    """Miller–Rabin primality test"""
    if n < 2:
        return False
    elif n in {2, 3, 5, 7, 11, 61}:
        return True
    elif n % 2 == 0 or n % 3 == 0 or n % 5 == 0 or n % 7 == 0 or n % 11 == 0:
        return False

    if n < (1 << 32):
        L = [2, 7, 61]
    elif n < (1 << 48):
        L = [2, 3, 5, 7, 11, 13, 17]
    else:
        L = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

    d = n - 1
    d = d // (d & -d)

    for a in L:
        y = pow(a, d, n)
        if y == 1:
            continue
        t = d
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1:
                return False
            t <<= 1
    return True


def find_factor_rho(n: int) -> Optional[int]:
    """Pollard's rho algorithm using Brent's cycle finding method"""
    if n < 2:
        return None
    m = 1 << n.bit_length() // 8 + 1

    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if is_prime_miller_rabin(g):
                return g
            elif is_prime_miller_rabin(n // g):
                return n // g
    return None


def prime_factorize(n: int) -> Dict[int, int]:
    """Prime factorize n in O(n^(1/4))?.
    https://twitter.com/kiri8128/status/1240504897419673600
    """
    prime_factors = defaultdict(int)
    i = 2
    while i * i <= n:
        while n % i == 0:
            n //= i
            prime_factors[i] += 1
        i += 1 + i % 2
        if i != 101 or n < 1 << 20:
            continue
        while n > 1:
            if is_prime_miller_rabin(n):
                prime_factors[n], n = 1, 1
                break
            j = find_factor_rho(n)
            while n % j == 0:
                n //= j
                prime_factors[j] += 1
    if n > 1:
        prime_factors[n] += 1
    return prime_factors  


def eulers_product_formula(n: int) -> int:
    """Calculate Euler's totient function.
    The time complexity depends on the implementation of prime factorization.
    """
    phi = n
    prime_factors = prime_factorize(n).keys()
    for p in prime_factors:
        phi *= 1 - (1 / p)
    return int(phi)


def main():
    N = int(input())
    print(eulers_product_formula(N))


if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
ans = n

prime = []
for i in range(2, int(n**0.5)+1):
    if n%i != 0:
        continue

    prime.append(i)

    while n%i == 0:
        n //= i

if n != 1:
    prime.append(n)

for p in prime:
    ans *= (1-1/p)

print(int(ans))

Solution (Python):
def prime_factorize(n):
    limit = int(n ** 0.5) + 1
    yakusu = []
    i = 2
    while i <= limit:
        while n % i == 0:
            n //= i
            yakusu.append(i)
        i += 1
    if not n == 1: 
        yakusu.append(n)

    return yakusu


import itertools


N = int(input())
F = prime_factorize(N)
F = list(set(F))
l = len(F)

s = 0
t = [i for i in range(l)]
for i in range(l):
    for a in itertools.combinations(t, i + 1):
        x = 1
        for k in a:
            x *= F[k]
        if i % 2 == 0:
            s += N // x
        else:
            s -= N // x

print(N - s)

Solution (Python):
import math

n = int(input())




def Euler(n):
    if n == 1 or n == 2:
        return 1
    else:
        a,b = 1,0
        for i in range(2,int(math.sqrt(n))+1):
            if n % i == 0:
                a = i 
                while n % a == 0:
                    n //= a
                    b += 1
                break
        if a == 1: 
            return n-1
        else:
            return (a**b-a**(b-1))*Euler(n)

print(Euler(n))

Solution (Python):
n = num = int(input())
i=2
while i * i <= n:
    if n % i ==0:
        num = num // i * (i - 1)
        while n % i == 0:
            n //= i
    i += 1
if n != 1 :
    num = num // n * (n - 1)
print(num)

Solution (Python):
def euler_phi(n):
    if n == 1: return 1
    res = 1
    x = n
    y = 2
    while y*y <= x:
        k = 0
        while x%y == 0:
            k += 1
            x //= y
        if k: res *= y**(k-1)*(y-1)
        y += 1
    if x > 1: res *= x-1
    return res
    
N = int(input())
print(euler_phi(N))

Solution (Python):
n  = int(input())
m = n
factors = set()
q = 2
while n>1 and q*q<=n:
	if n % q == 0:
		factors.add(q)
		n //= q
	else:
		q += 1
if n>1:
	factors.add(n)

for p in factors:
	m *= p-1
	m //= p

print(m)

Solution (Python):
def factoring(n):
    """
    This program factorize any number.
    This returns the dictionary of prime factors of the number.(if n=18=2*3**2, this returns {2:1,3:2})
        """
    if n == 0:
        return {0: 1}
    if n == 1:
        return {1: 1}

    
    
    

    nOrigin = n
    n = n**0.5
    
    
    
    numlist = [0 for i in range(int(n) + 1)]
    numlist[0] = -1
    numlist[1] = -1

    
    t = 2
    while t < (n**0.5):
        if numlist[t] == 0:
            numlist[t] = t
            k = 2
            while t * k <= n:
                numlist[t * k] = -1
                k += 1
        t += 1

    
    while t <= n:
        if numlist[t] == 0:
            numlist[t] = t
        t += 1

    
    result = {}
    for i in numlist:
        if i == -1:
            continue
        j = 0
        while nOrigin % i == 0:
            j += 1
            nOrigin = nOrigin / i
        if j == 0:
            continue
        else:
            result[i] = j

    if int(nOrigin) != 1:
        result[int(nOrigin)] = 1
    return result


n=int(input())

fact=factoring(n)
retval=1
for i in fact.items():
    retval*=(i[0]**i[1]-i[0]**(i[1]-1))
print(retval)

Solution (Python):
def f(num):
   i = 2
   d = dict()
   while i * i <= num:
       if num % i == 0:
           num //= i
           d[i] = d.get(i, 0) + 1
       else:
           i += 1
   
   d[num] = d.get(num, 0) + 1
   return d

n = int(input())
d = f(n)

ans = n
for k in d.keys():
    ans *= (1-(1/k))

print(int(ans))

Solution (Python):
n=int(input())
ans=n

i=2
while i**2<=n:
    if n%i==0:
        ans=(ans-(ans//i))
        while n%i==0:
            n//=i
    i+=1

if n!=1:
    ans=(ans-(ans//n))

print(ans)

Solution (Python):
def euler_totient(n):
    if n <= 0:
        return 0
    ans = n
    i = 2
    while i * i <= n:
        if n % i == 0:
            ans -= ans // i
            while n % i == 0:
                n //= i
        i += 1
    if n > 1:
        ans -= ans // n
    return ans


def aoj():
    print(euler_totient(int(input())))


if __name__ == "__main__":
    aoj()

Solution (Python):
def factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def factorize2(n):
    plist = factorize(n)
    dic = {}
    for n in plist:
        if not n in dic:
            dic[n] = 1
        else:
            dic[n] += 1
    ret = []
    for p,n in dic.items():
        ret.append([p,n])
    return ret

def phi(n):
    plist = factorize2(n)
    ans = 1
    for [p,n] in plist:
        ans *= (pow(p,n)-pow(p,n-1))
    return ans

Q = int(input())
print(phi(Q))

Solution (Python):

import math
N = int(input())
fact = []
n2 = math.ceil(math.sqrt(N))
n = N
for i in range(n2):
    I = i+1
    if I == 1:
        continue
    flag = 0
    if N%I == 0:
        flag = 1
    count = 0
    while N%I == 0:
        N = N//I
        count+=1
    if flag == 1:
        fact.append([I,count])
    
if N != 1:
    fact.append([N,1])

    
ans = n
for f in fact:
    p,c = f
    ans*=(1-1/p)
    
print(int(ans))

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def factorize(num: int) -> dict:
    """ 素因数分解 """
    from math import sqrt
    from collections import Counter

    d = Counter()
    
    for i in range(2, int(sqrt(num))+1):
        
        while num % i == 0:
            num //= i
            d[i] += 1
        
        if num == 1:
            break
    
    if num != 1:
        d[num] += 1
    return d

N = INT()

primes = factorize(N)
ans = N

for k in primes.keys():
    ans *= 1 - 1/k
print(int(ans))

Solution (Python):
import math
import sys

i=int(input())
def prime(i):
  k=[]
  num=i
  j=2
  while j*j<=num:
    if i%j==0:
      i//=j
      k.append(j)
    else:
      j+=1
  if i!=1:
    k.append(i)
  

  return k

j=set(prime(i))
ans=i
for z in j:
  ans*=(1-1/z)
  
print(int(ans))

Solution (Python):
import math

N = int(input())

def soinsuu(N):
    d = 2
    divs = set()
    while d*d <= N:
        if N%d == 0:
            divs.add(d)
            while N%d == 0: N //= d
        d += 1
    if N != 1:
        divs.add(N)
    return divs

divs = list(soinsuu(N))

L = len(divs)
ans = 0
for bit in range(1<<L):
    tmp = 1
    cnt = 0
    for b in range(L):
        if bit & (1<<b):
            tmp *= divs[b]
            cnt += 1

    if cnt%2 == 1:
        ans -= N//tmp
    else:
        ans += N//tmp

print(ans)

Solution (Python):
def prime_factorization(n) -> list:
	if n==1:
		return [1]
	ret = []
	i = 2
	while i*i<=n:
		while n%i==0:
			n //= i
			ret.append(i)
		i += 1
	if n!=1:
		ret.append(n)
	return ret
n=int(input())
from functools import reduce
from operator import mul
pf=set(prime_factorization(n))
print(int(reduce(mul,[n]+[1-1/p for p in pf])))

Solution (Python):
import math
import fractions
from typing import List


def compute_prime_factor(n: int) -> None:
    global prime_factors
    sqrt_n = int(math.sqrt(n)) + 1
    for i in range(2, sqrt_n + 1):
        if 0 == (n % i):
            prime_factors.append(i)
            compute_prime_factor(n // i)
            return
    if 1 != n:
        prime_factors.append(n)
        return


def euler_phi(n: int, prime_factors: List[int]) -> int:
    distinct_factors = set(prime_factors)
    result = 1
    for f in distinct_factors:
        result *= (1 - fractions.Fraction(1, f))
    result *= n
    return result.numerator


if __name__ == "__main__":
    n = int(input())
    prime_factors = []  
    compute_prime_factor(n)
    print(euler_phi(n, prime_factors))

Solution (Python):
n=int(input())
m=int(n**(1/2))

F=[]
n1=n
k=2

while k<=m:
    if n%k==0:
        F.append([k,1])
        n//=k
        
        while n%k==0:
            F[-1][1]+=1
            n//=k
    k+=1

if n>m:
    F.append([n,1])
product=1
l=len(F)
for i in range(l):
    product=product*((F[i][0]**(F[i][1]-1))*(F[i][0]-1))
print(product)

Solution (Python):
from collections import defaultdict
from fractions import gcd
n=int(input())
def prime_factor(n):
    i = 2
    table = defaultdict(int)
    while i * i <= n:
        while n % i == 0:
            n //= i
            table[i]+=1
        i += 1
    if n > 1:
        table[n]+=1
    return table
table=prime_factor(n)
d=list(table.keys())
ans=n
for i in d:
    ans*=(1-1/i)
print(int(ans))

Solution (Python):
n=m=int(input())
i=2
while i*i<=n:
    if n%i==0:
        m=m//i*(i-1)
        while n%i==0: n//=i
    i+=1
if n!=1:m=m//n*(n-1)
print(m)

Solution (Python):
n = int(input())
answer = n

i = 2
while i ** 2 <= n:
    if n % i == 0:
        answer *= (1 - 1 / i)

        while n % i == 0:
            n //= i

    i += 1

if n != 1:
    answer *= (1 - 1 / n)

print(int(answer))

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l(): 
	return list(map(int,input().split()))
def m(): 
	return map(int,input().split())
def onem(): 
	return int(input())
def s(x): 
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): 
	return " ".join(map(str,x))
def max2(x): 
	return max(map(max,x))

def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(int(n))
  return table

n = onem()
nn = prime_decomposition(n)
l = cl.Counter(nn)

kkk = 1
for i,j in l.items():
	kkk *= (i-1) * (i ** (j-1))

print(kkk)

Solution (Python):
def euler_phi(n):
    res = n
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            while n % i == 0:
                n //= i
            res -= res // i
    if n > 1:
        res -= res // n
    return res

n = int(input())
print(euler_phi(n))

Solution (Python):
import math

def primes(n):
    rn = int(math.sqrt(n))
    sieve = [1] * (rn + 1)
    for i in range(2, rn + 1):
        j = i * 2
        while j <= rn:
            sieve[j] = 0
            j += i
    p = [i for i in range(2, rn + 1) if sieve[i] == 1]
    return p

def phi_func(n, p):
    ans = n
    for q in p:
        if n % q == 0:
            ans = ans * (q - 1) // q
            while n % q == 0:
                n //= q
    else:
        if n > 1:
            ans = ans * (n - 1) // n
    return ans

line = input()
n = int(line)
p = primes(n)
print(phi_func(n, p))

Solution (Python):
def phi(n):
  ret=1
  rem=1
  for i in range(2,int(n**0.5)+1):
    if n%i==0:
      ret*=i-1
      n=n//i
      while n%i==0:
        n=n//i
        rem*=i
  if n>1:
    ret*=n-1
  return ret*rem
 
n=int(input())
print(phi(n))

Solution (Python):

import math
n = m =int(input())
i = 2
while i <= math.sqrt(n):
    if n%i == 0:
        m = int(m*(1-1/i))
        while n%i == 0:n //=i
    i+=1
if n != 1:m = int(m*(1-1/n));
print(m)

Solution (Python):
from collections import defaultdict
from itertools import combinations
from functools import reduce
n = int(input())
r = int(n ** (1 / 2)) + 2
dic = defaultdict(int)
temp = n
for i in range(2, r):
  if temp < i:
    break
  while temp % i == 0:
    temp //= i
    dic[i] += 1
if temp != 1:
  dic[temp] += 1

ans = n
keys = list(dic.keys())
length = len(keys)
for i in range(1, length + 1):
  for t in combinations(keys, i):
    ans += n // reduce(lambda x, y:x * y, t) * (-1) ** i
print(ans)

Solution (Python):
from itertools import takewhile
from functools import reduce


def gen_prime_candidates():
    yield 2
    yield 3
    n = 0
    while 1:
        yield n + 5
        yield n + 7
        n += 6


def calc_exp(n, p):
    e = 0
    while n % p == 0:
        e += 1
        n /= p
    return e, n


def factorize(n):
    f = ()
    for p in takewhile(lambda p: p * p <= n, gen_prime_candidates()):
        e, n = calc_exp(n, p)
        if e:
            f += (p, )
    if n > 1:
        f += (n, )
    return f


def phi(n):
    return reduce(lambda x, p: x * (p-1) / p, factorize(n), n)


n = int(input())
print(int(phi(n)))

Solution (Python):
import sys,math

n=m=int(input())
c=0
def factorint(N):
    i=2
    fct=[]
    while i**2<=N:
        if N%i!=0:
            i+=1
        else:
            N//=i
            fct.append(i)
    if N>1:
        fct.append(N)
    return fct
l1=factorint(n)
l2=list(set(l1))



if len(l1)==len(l2):
    ans=1
    for item in l2:
        ans*=(item-1)
else:
    l3=[]
    x=1
    for i in range(len(l2)):
        for j in range(i,len(l2)):
            if i!=j:
                l3.append(l2[i]*l2[j])
        x*=l2[i]
    l4=[n//item for item in l2]
    l5=[n//item for item in l3]
    if len(l2)>2:
        y=n//x
    else:
        y=0
    ans=(n-(sum(l4)-sum(l5)+y))





print(ans)

Solution (Python):


from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

n_ = n = input()

ls = []
for i in range(2, int(math.sqrt(n) + 1)):
    if n % i == 0:
        ls.append(i)
    while n % i == 0:
        n /= i

if n != 1:
    ls.append(n)

ans = 0

for i in range(2 ** len(ls)):
    den = 1
    sign = 1
    for j in range(len(ls)):
        if i & (1 << j):
            den *= ls[j]
            sign *= -1
    ans += n_ / den * sign

print ans

Solution (Python):
import math
n=int(input())
n1=n
b=int(math.sqrt(n))+1

phai=1

if n!=1:
    for i in range(2,b):
        i_count=0
        while n%i==0:
            i_count+=1
            n=n//i
        if i_count!=0:
            phai=phai*(1-1/i)

    if n!=0 and n!=1:
        phai=phai*(1-1/n)

    phai=phai*n1
    if phai-int(phai)>0.8:
        phai=int(phai)+1
    else:
        phai=int(phai)
else:
    phai=0
print(phai)

Solution (Python):
import math

n = int(input())

soinsu = []

c = n
if (c % 2 == 0):
    while True:
        soinsu.append(2)
        c = c // 2
        if ( c % 2 != 0):
            break

len = int(math.sqrt(c)) + 1
for i  in range (3,len,2):
    while True:
        if ( c % i != 0):
            break
        soinsu.append(i)
        c = c // i
    if ( c == 1):
        break
if ( c != 1):
    soinsu.append(c)

d = n
for i in set(soinsu):
    d = d * (1-(1/i))
print (int(d))

Solution (Python):
import functools
import operator
n = int(input())
import math
def factorization(n):
    def factor_sub(n, m):
        c = 0
        while n % m == 0:
            c += 1
            n /= m
        return c, n
    
    buff = []
    c, m = factor_sub(n, 2)
    if c > 0: buff.append((2, c))
    c, m = factor_sub(m, 3)
    if c > 0: buff.append((3, c))
    x = 5
    while m >= x * x:
        c, m = factor_sub(m, x)
        if c > 0: buff.append((x, c))
        if x % 6 == 5:
            x += 2
        else:
            x += 4
    if m > 1: buff.append((m, 1))
    return buff
  
a = factorization(n)
b = []
for i,j in a:
  b.append(i)
import itertools
ans = n
for i in range(1,len(b)+1):
  c = list(itertools.combinations(b,i))
  for j in c:
    kake = functools.reduce(operator.mul, j)
    if i %2 == 1:
      ans -= n//kake
    else:
      ans += n//kake
print(int(ans))

Solution (Python):
import math

n = int(input())
m = n
ans = []
i = 2
k = math.sqrt(n)
dic = {}
while i <= k:
    if n%i == 0:
        n = n//i
        ans.append(i)
        i -= 1
        if n == 1:
            break
    i += 1
if len(ans) == 0 or n != 1:
    ans.append(n)
ans = list(set(ans))
sum = m
for i in ans:
    sum *= (1-1/i)
print(int(sum))

Solution (Python):
n = m = int(input())
i = 2
while i ** 2 <= n:
    if n % i == 0:
        m = m // i * (i - 1)
        while n % i == 0:
            n //= i
    i += 1
if n != 1:
    m = m // n * (n - 1)
print(m)

Solution (Python):
def phi(n):
	result = n
	for i in range(2, n + 1):
		if i ** 2 > n:
			break
		elif n % i == 0:
			while n % i == 0:
				n /= i
			result -= result / i
	if n > 1:
		result -= result / n
	return int(result)

print(phi(int(input())))

Solution (Python):
from collections import Counter

n = int(input())
prime_list = []
while n > 1:
    k = 2
    while k ** 2 <= n:
        if n % k == 0:
            prime_list.append(k)
            n //= k
            break
        else:
            k += 1
    else:
        prime_list.append(n)
        n = 1
prime_fact = Counter(prime_list)
ans = 1
for p, k in prime_fact.items():
    ans *= (p ** (k - 1) )*(p - 1)
print(ans)

Solution (Python):
n=int(input())
ans=n
i=2
while i*i<=n:
    if  n%i==0:
        while n%i==0:
            n//=i
        ans=ans*(i-1)//i
    i+=1
if n!=1:ans=ans*(n-1)//n
print(ans)