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):
import math
from collections import defaultdict

def prime_factorize(n: int):
    prime_factors = defaultdict(int)

    for i in range(2, int(math.sqrt(n)) + 1):
        while True:
            div, mod = divmod(n, i)
            if mod == 0:
                prime_factors[i] += 1
                n = div
            else:
                break
        if n == 1:
            break
    if n != 1:
        prime_factors[n] = 1

    return prime_factors


def main():
   n = int(input())
   primes = prime_factorize(n)

   ret = 1
   for k, v in primes.items():
      ret *= pow(k, v) - pow(k, v-1)
   print(ret)
   return



main()

Solution (Python):
from fractions import Fraction
def prime(num):
    prime_list = []
    temp = num
    div = 2
    while temp > 1 and temp >= div ** 2:
        if temp % div == 0:
            prime_list.append(div)
            temp //= div
        else:
            div += 1
    if temp != 1:
        prime_list.append(temp)
    return prime_list

target = int(input())
prime_list = prime(target)
answer = target

for p in set(prime_list):
    answer *= (1 - Fraction(1, p))
print(answer)

Solution (Python):
from subprocess import*
from collections import*
n=int(input())
p=Counter(map(int,Popen(["factor",str(n)],stdout=PIPE).communicate()[0].decode().split()[1:]))
a=n
for i in p:
    a=a//i*~-i
print(a)

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

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

Solution (Python):
import sys

def sieve(n):
    is_prime = [True] * (n + 1)
    prime_list = []
    
    is_prime[0] = is_prime[1] = False
    prime_list.append(2)
    
    for i in range(3, n + 1, 2):
        if is_prime[i]: prime_list.append(i)
        for j in range(i * i, n + 1, i):
            is_prime[j] = False
    return prime_list
    
primes = sieve(40000)

def factoriaztion(n):
    ret = []
    for prime in primes:
        cc = 0
        while n % prime == 0:
            cc += 1
            n /= prime
        if cc != 0: ret.append((prime, cc))
        if n == 1: break
    if n > 1: ret.append((n, 1))
    return ret
    
    
if __name__ == '__main__':
    n = sys.stdin.readline()
    n = int(n)
    factors = factoriaztion(n)
    
    ans = reduce(lambda acc, (x, m) : acc * (x ** m - x ** (m - 1)), factors, 1)
    
    sys.stdout.write(str(ans) + '\n')

Solution (Python):
import sys

def sieve(n):
    is_prime = [True] * (n + 1)
    prime_list = []
    
    is_prime[0] = is_prime[1] = False
    prime_list.append(2)
    
    for i in range(3, n + 1, 2):
        if is_prime[i]: prime_list.append(i)
        for j in range(i * i, n + 1, i):
            is_prime[j] = False
    return prime_list
    
primes = sieve(40000)

def factoriaztion(n):
    ret = []
    for prime in primes:
        cc = 0
        while n % prime == 0:
            cc += 1
            n /= prime
        if cc != 0: ret.append((prime, cc))
        if n == 1: break
    if n > 1: ret.append((n, 1))
    return ret
    
    
if __name__ == '__main__':
    n = sys.stdin.readline()
    n = int(n)
    factors = factoriaztion(n)
    
    ans = reduce(lambda acc, (x, m) : acc * (x ** m - x ** (m - 1)), factors, 1)
    
    sys.stdout.write(str(ans) + '\n')

Solution (Python):
import sys
import itertools

def sieve(n):
    is_prime = [True] * (n + 1)
    prime_list = []
    
    is_prime[0] = is_prime[1] = False
    prime_list.append(2)
    
    for i in range(3, n + 1, 2):
        if is_prime[i]: prime_list.append(i)
        for j in range(i * i, n + 1, i):
            is_prime[j] = False
    return prime_list
    
primes = sieve(40000)

def factoriaztion(n):
    ret = []
    for prime in primes:
        while n % prime == 0:
            ret.append(prime)
            n /= prime
        if n == 1: break
    if n > 1: ret.append(n)
    return ret
    
    
if __name__ == '__main__':
    n = sys.stdin.readline()
    n = int(n)
    factors = factoriaztion(n)
    factors = itertools.groupby(factors)
    
    ans = 1
    
    for k, v in factors:
        l = len(list(v))
        ans = ans * (k ** l - k ** (l - 1))
    
    sys.stdout.write(str(ans) + '\n')

Solution (Python):
import math
def sieve(n):
    p = [1] * (n + 1)
    p[0] = p[1] = 0
    
    for i in range(math.ceil((n + 1) ** 0.5)):
        if p[i]:
            for j in range(2 * i, len(p), i):
                p[j] = 0
    return p

from itertools import compress, count
def prime_factor(n):
    p = sieve(int(n ** 0.5))
    factor = []
    for pi in compress(count(0), p):
        while n % pi == 0:
            n //= pi
            factor.append(pi)

    if n != 1:
        factor.append(n)
    return factor

from sys import stdin
from functools import reduce
from operator import mul
from collections import Counter
readline = stdin.readline

print(reduce(mul, (pow(p, k) - pow(p, k - 1) for p, k in Counter(prime_factor(int(readline()))).items())))

Solution (Python):
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(n)
    return table

def phi_pk(p,k):
    return (p-1)*p**(k-1)

def pkcounter(ls):
    dic={}
    for i in ls:
        dic[i]=dic.get(i,0)
        dic[i]+=1
    return dic

n = int(raw_input())
table = prime_decomposition(n)
dic = pkcounter(table)
ans=1
for k,v in dic.items():
    ans *= phi_pk(k,v)
print ans

Solution (Python):
from __future__ import division

maxn = 40000

def sieve(n):
    ret = []
    isPrime = [False if i % 2 == 0 else True for i in range(n + 1)]
    isPrime[0] = isPrime[1] = False
    ret.append(2)
    for i in range(3, n + 1, 2):
        if isPrime[i]:
            ret.append(i)
            for j in range(i * i, n + 1, i):
                isPrime[i] = False

    return ret

primes = sieve(maxn)

def factor(n):
    ret, idx = [], 0
    for p in primes:
        if n % p == 0:
            count = 0
            while n % p == 0:
                count += 1
                n //= p
            ret.append((p, count))

    if n > 1: ret.append((n, 1))
    return ret

def euler_phi(n):
    facts = factor(n)
    return reduce(lambda acc, (p, a):  acc * (p ** a - p ** (a - 1)), facts, 1)


if __name__ == '__main__':
    n = int(raw_input())
    print euler_phi(n)

Solution (Python):
def p(n):
    l = [1]*(n+1)
    l[0] = l[1] = 0
    for i in range(2,int(n ** 0.5) + 1):
        if l[i]:
            for j in range(2*i, n+1, i):
                l[j] = 0
    return l
n = input()
ans = n
l = set()
from itertools import compress
P = p(int(n ** 0.5))
for i in compress(xrange(0,n), P):
    while n % i == 0:
        n /= i
        l.add(i)
if n != 1: l.add(n)
for i in l:
    ans = ans * (i - 1) / i
print ans

Solution (Python):
from math import sqrt, floor
from collections import deque
from functools import reduce
from operator import mul


def divide(p):
    global n, a, limit
    while not (n % p):
        a.add(p)
        n = n // p
        limit = floor(sqrt(n))


n, p = int(input()), 3
n0 = n
limit = floor(sqrt(n))
a, i = set(), 3

divide(2)

while p <= limit:
    divide(p)
    p += 2

if n > 1:
    a.add(n)

print(reduce(lambda prev, now: prev * (now - 1) // now, a, n0))

Solution (Python):
from math import sqrt, floor
from functools import reduce


def divide(p):
    global n, a, limit
    while not (n % p):
        a.add(p)
        n = n // p
        limit = floor(sqrt(n))


n, p = int(input()), 3
n0 = n
limit = floor(sqrt(n))
a, i = set(), 3

divide(2)

while p <= limit:
    divide(p)
    p += 2

if n > 1:
    a.add(n)

print(reduce(lambda prev, now: prev * (now - 1) // now, a, n0))

Solution (Python):



import collections
import fractions
import itertools


def prime_factorization(n):

    assert n > 0
    if n == 1:
        return collections.deque([1])
    else:
        result = collections.deque()
        for i in itertools.count(2):
            if i * i > n:
                break
            else:
                while n % i == 0:
                    n //= i
                    result.append(i)
        if n > 1:
            result.append(n)
        return result


def phi(n):
    distinct_factors = set(prime_factorization(n))
    result = 1
    for f in distinct_factors:
        result *= (1 - fractions.Fraction(1, f))
    result *= n
    return result


if __name__ == "__main__":
    print(phi(int(input())))

Solution (Python):
import math
def calc(d):
    k = 1
    for key in d.iterkeys():
        if d[key] != 0:
            k *= (int(key) ** (d[key]-1)) * (int(key)-1)
    return k

n = input()

prime = []

m = int(math.sqrt(n))
for i in range(m+1):
    prime.append(True)

prime[0] = False
prime[1] = False

for i in range(2, int(math.sqrt(m))):
    if not prime[i]:
        continue
    else:
        for j in range(i+1, int(math.sqrt(m))):
            if j % i == 0:
                prime[j] = False

s = []
i = 2
num = n
while True:
    if i == int(math.sqrt(num))+1:
        s.append(str(n))
        break

    if not prime[i] or n % i != 0:
        i += 1
        continue

    if n % i == 0:
        s.append(str(i))
        n /= i
        if n == 1:
            break

tmp_dict = {}
for c in s:
    if not c in tmp_dict.keys():
        tmp_dict[c] = 1
    else:
        tmp_dict[c] += 1

print "%d" % calc(tmp_dict)

Solution (Python):
import collections

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

n = int(input())
freq = collections.Counter(prime_decomposition(n))
ans = n
for k,v in freq.items():
    ans *= (1-1/k)
print(int(ans))

Solution (Python):
def soi(n): 
    i=2
    while True:
        if i*i>n:
            return n
        
        if n%i==0:
            return i
        i+=1


a=int(input())
ans=a
count=1
i=2 
while True:
    temp=soi(a)
    if a==1: 
        break
    while a%temp==0: 
        a/=temp
     

    ans*=(1-1/temp)
    

print(int(ans))


                
       

def gcd(a,b): 
    r=0
    while True:
       r=a%b
       if r==0:
           break
       a=b
       b=r
    return b

Solution (Python):
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(n)
    return table
n = input()
pdlist = prime_decomposition(n)
pdset = set(pdlist)
if len(pdlist)==1:
    for x in pdset:
        print x-1
else:
    ans = n
    for x in pdset:
        ans *= 1-1.0/x
    print int(ans)

Solution (Python):
def primefactor(x):
    fac=[]
    for i in xrange(2,int(x**0.5)+1):
        while x%i==0:
            fac+=[i]
            x=x/i
    if x!=1:
        fac+=[x]
    return fac
n=input()
anslist=list(set(primefactor(n)))
ans=n
for i in anslist:
    ans=ans*(1-1.0/i)
print(int(ans))

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

Solution (Python):



"""
input:
1000000

output:
400000
"""

import sys


def soi(n):
    k = 2
    while True:
        if pow(k, 2) > n:
            return n
        if n % k == 0:
            return k
        k += 1


def phi(n):
    ans = n
    while True:
        tmp = soi(n)
        
        if n == 1:
            break
        while n % tmp == 0:
            n //= tmp
        ans *= (1 - 1 / tmp)
    return int(ans)


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    n1 = int(_input[0])
    print(phi(n1))

Solution (Python):



"""
input:
1000000

output:
400000
"""

import sys


def min_prime_factor(n):
    k = 2
    while True:
        if pow(k, 2) > n:
            return n
        if not n % k:
            return k
        k += 1


def phi(n):
    ans = n
    while True:
        p = min_prime_factor(n)
        if n == 1:
            break
        while not n % p:
            n //= p
        ans *= (1 - 1 / p)
    return int(ans)


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    n1 = int(_input[0])
    print(phi(n1))

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())

def function(n):
    a = []
    if n < 2:
        return a
    while n%2 ==0:
        a.append(2)
        n = n//2
    i = 3
    while i*i <= n:
        if n%i ==0:
            a.append(i)
            n = n//i
        else:
            i += 2
    if n > 1:
        a.append(n)
    return a



for k in set(function(n)):
    n *= (1-1/k)
print(int(n))

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

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

print(ans)

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

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

Solution (Python):


import itertools
import sys, math, os


PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


def get_factors(n):
    f = 2
    increments = itertools.chain([1,2,2], itertools.cycle([4,2,4,2,4,6,2,6]))
    for incr in increments:
        if f*f > n:
            break
        while n % f == 0:
            yield f
            n //= f
        f += incr
    if n > 1:
        yield n

N = int(input())
totient = N
for p in list(set(get_factors(N))):
    totient *= (1 - 1 / p)
print(int(totient))

Solution (Python):
def is_prime(x):
    
    return pow(2, x - 1, x) == 1

def solve():
    n = int(input())
    ans = n
    if n % 2 == 0:
        ans -= ans // 2
        while n % 2 == 0:
            n //= 2
    d = 3
    while d <= n ** 0.5:
        if is_prime(d) and n % d == 0:
            ans -= ans // d
            while n % d == 0:
                n //= d
        d += 2
    if is_prime(n):
        ans -= ans // n
    print(ans)

solve()

Solution (Python):
import sys
def euler(a):
    i = 2
    res = a
    
    while i * i <= a:
        if a % i == 0:
            res = res - res//i
            while a % i == 0:
                a //= i

        i += 1
    if a != 1:
        res = res - res//a

    return res


x = int(input())


print(euler(x))

Solution (Python):
def solve():
    from math import sqrt
    N = n = int(input())
    primes = [] if n%2 else [2]
    while n%2 == 0:
        n //= 2
    for i in range(3, int(sqrt(n)), 2):
        if n % i == 0:
            primes.append(i)
            while n % i == 0:
                n //= i
    if n != 1:
        primes.append(n)

    numer, denom = N, 1
    for prime in primes:
        numer *= prime-1
        denom *= prime

    print(numer//denom)


if __name__ == "__main__":
    solve()

Solution (Python):
p=1;a=[]
n=int(input());s=n**.5
while n%2==0 and n>3:a+=[2];n//=2
d=3
while s>d and n>d:
 if n%d==0:a+=[d];n//=d
 else:d+=2
a+=[n]
for f in set(a):
 p*=f**a.count(f)*(1-1/f)
print(int(p))

Solution (Python):
d=3;a=[]
n=int(input());s=n**.5
while n%2==0 and n>3:a+=[2];n//=2
while s>d and n>d:
 if n%d>0:d+=2
 else:a+=[d];n//=d
a+=[n];p=1
for f in set(a):
 p*=f**a.count(f)*(1-1/f)
print(int(p))

Solution (Python):

d=3;a=[]
n=int(input());s=n**.5
while n%2==0 and n>3:a+=[2];n//=2
while s>d and n>d:
 if n%d>0:d+=2
 else:a+=[d];n//=d

a+=[n];p=1
for f in set(a):
 p*=f**a.count(f)*(1-1/f)
print(int(p))

Solution (Python):
d=3;a=[]
n=int(input());s=n**.5
while n%2==0 and n>3:a+=[2];n//=2
while s>d and n>d:
 if n%d>0:d+=2
 else:a+=[d];n//=d
a+=[n];p=1
for f in set(a):
 p*=f**a.count(f)*(1-1/f)
print(int(p))

Solution (Python):
a=[]
n=int(input());s=n**.5
while n%2==0 and n>3:a+=[2];n//=2
d=3
while s>d and n>d:
 if n%d>0:d+=2
 else:a+=[d];n//=d
a+=[n]
p=1
for f in set(a):
 p*=f**a.count(f)*(1-1/f)
print(int(p))

Solution (Python):
p=n=int(input())
d=2
while d*d<=n:
 if n%d==0:
  p=p*(d-1)//d
  while n%d==0:n//=d
 d+=1
if n>1:p=p*(n-1)//n
print(p)

Solution (Python):
f=lambda x:p*(x-1)//x
p=n=int(input())
d=2
while d*d<=n:
 if n%d==0:
  p=f(d)
  while n%d==0:n//=d
 d+=1
if n>1:p=f(n)
print(p)

Solution (Python):
p=n=int(input())
d=2
while d*d<=n:
 if n%d==0:
  p=p*(d-1)//d
  while n%d==0:n//=d
 d+=1
print([p,p*(n-1)//n][n>1])

Solution (Python):
import math

def eulers_phi_function(n):
    s = math.sqrt(n)
    x = n
    rst = n
    for y in range(2, math.ceil(s)):
        if x == 1: break
        while True:
            if x%y == 0:
                rst *= 1 - 1/y
                while x%y == 0:
                    x = x/y
            else:
                break
    if x > s: rst *= 1 - 1/x
    return int(rst)

n = int(input())
print(eulers_phi_function(n))

Solution (Python):
n = int(input())
def prime_factorize(n):
	import math
	m = math.sqrt(n)+1
	i = 2
	prime = {}
	while n != 1 and i < m:
		if n % i == 0:
			if i in prime:
				prime[i] += 1
			else:
				prime[i] = 1 
			n //= i
		else:
			i += 1
	if n != 1:
		prime[n] = 1
	return prime

dic = prime_factorize(n)
for key in dic.keys():
	n *= (1 - (1/key))

print(int(n))

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

n = int(raw_input())
print phi(n)

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

def factorize(N):
    arr = []
    for x in range(2, int(pow(N, 0.5) + 1)):
        cnt = 0
        while N % x == 0:
            cnt += 1
            N = N // x

        if cnt > 0:
            arr.append((x, cnt))

    if N != 1:
        arr.append((N, 1))

    return arr

euler = 1
for p, m in factorize(n):
    euler *= pow(p,m) - pow(p,m-1)

print(euler)

Solution (Python):
import sys
from itertools import product

input = sys.stdin.readline


def calc_prime_factors(n, count=False):
    """Trial division"""
    factors = []
    
    while n % 2 == 0:
        factors.append(2)
        n //= 2
    
    f = 3
    root_n = int(n ** 0.5) + 1
    while f <= root_n:
        if n % f == 0:
            factors.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        factors.append(n)
    return factors


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

    factors = calc_prime_factors(N)
    factors = list(set(factors))
    ans = N
    for comb in product(range(2), repeat=len(factors)):
        div = 1
        cnt = 0
        for i, c in enumerate(comb):
            if c == 1:
                cnt += 1
                div *= factors[i]
        if cnt == 0:
            continue
        coeff = -1 if cnt % 2 == 1 else 1
        ans += coeff * (N // div)

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
res = n
l = []
i = 2
while i * i <= n:
    while n % i == 0:
        l.append(i)
        n //= i
    i += 1
if n != 1:
    l.append(n)
l = set(l)
for i in l:
    res *= (1 - 1 / i)
print(int(res))

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n = int(input())
prime_factors = []

i = 2
copy_n = n
while i ** 2 <= copy_n:
    ext = 0
    while copy_n % i == 0:
        ext += 1
        copy_n //= i
    if ext:
        prime_factors.append((i, ext))
    i += 1
if copy_n != 1:
    prime_factors.append((copy_n, 1))

for pf, _ in prime_factors:
    n *= (pf - 1)
    n //= pf
print(n)

Solution (Python):
N = int(input())
orgN = N
div = []

def bitsoncount(x):
    return bin(x).count('1')

for d in range(2, N):
    if d*d > N:
        break
    if N % d == 0:
        div.append(d)
        while N % d == 0:
            N = N // d
if N != 1: div.append(N)

M = len(div)
ans = 0
for i in range(1, 2 ** M): 
    mul = 1
    bc = bitsoncount(i)
    for m in range(M):
        if i >> m & 1:
            mul *= div[m]
    if bc % 2 == 1:
        ans += orgN // mul
    else:
        ans -= orgN // mul

ans = orgN - ans
print(ans)

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

sosu = []
for i in range(2, int(pow(n, 0.5)) + 1):
    if n % i == 0:
        sosu.append(i)
        if i != n // i:
            sosu.append(n // i)

if sosu == []:
    print(n - 1)
    exit()
yakusu = []
tmpn = n
while n > 1:
    index = 2
    while True:
        if n % index == 0:
            yakusu.append(index)
            n //= index
            break
        else:
            index += 1

yakusu = list(set(yakusu))
ans = tmpn
for i in yakusu:
    ans *= (1 - (1 / i))

print(int(ans))

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())


def factor(n, m=None):
    
    arr = {}
    temp = n
    M = int(-(-n**0.5//1))+1
    if m is not None:
        M = min(m+1, M)
    for i in range(2, M):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr[i] = cnt

    if temp!=1:
        arr[temp] = 1

    if not arr:
        arr[n] = 1

    return arr
d = factor(n)
ks = list(d.keys())
l = len(ks)
ans = 0
for b in range(1<<l):
    v = 1
    s = 0
    for i in range(l):
        if b>>i&1:
            v *= ks[i]
            s += 1
    ans += (n//v) * pow(-1, s)
print(ans)

Solution (Python):
def main():
    N = int(input())

    def prime_factorize(n):
        res = []
        for i in range(2, n+1):
            if i*i > n:
                break
            if n % i != 0:
                continue
            ex = 0
            while n % i == 0:
                ex += 1
                n //= i
            res.append((i, ex))
        if n != 1:
            res.append((n, 1))
        return res

    def euler_totient_function(n):
        
        
        pf = prime_factorize(n)
        res = n
        for p, _ in pf:
            res *= p-1
            res //= p
        return res

    print(euler_totient_function(N))


if __name__ == '__main__':
    main()

Solution (Python):


n = int(input())


def prime_divide(n):
    res = []
    i = 2
    while True:
        if n % i == 0:
            res.append(i)
            n //= i
        else:
            i += 1
            if i > n ** (0.5):
                break
    if n != 1:
        res.append(n)
    return res


def euler_fai(n):
    
    
    
    total = n  
    lis = list(set(prime_divide(n)))
    l = len(lis)
    
    for i in range(1, 2 ** l):
        cum = 1  
        cnt = 0
        for j in range(l):
            if i >> j & 1:
                
                cum *= lis[j]
                cnt += 1
        if cnt % 2:  
            total -= n // cum
        else:
            total += n // cum
    return total


print(euler_fai(n))

Solution (Python):
n = int(input())
def decomp(a):
    sqrt = round(n ** 0.5 + 0.5)
    factors = []
    for i in range(2, sqrt + 1):
        if not a % i:
            factors.append(i)
            while a % i == 0:
                a //= i
    if a != 1:
        factors.append(a)
    return factors
phi = n
for i in decomp(n):
    phi *= ((i - 1) / i)
print(int(phi))

Solution (Python):
def pfact(m):
	pf = {}
	for i in range(2,int(m**0.5)+1):
		while m%i == 0:
			pf[i] = pf.get(i,0) + 1
			m //= i
	if m>1 : pf[m]=1
	return pf

def euler(m):
	tmp = pfact(m)
	ans = 1
	for i, j in tmp.items():
		ans = ans * (i**(j-1)) * (i-1)
	return ans

n = int(input())
print(euler(n))

Solution (Python):
def factrize(x):
    
    f = {}
    tmp = x
    i = 2
    while i**2 <= tmp:
        cnt = 0
        while tmp % i == 0:
            cnt += 1
            tmp = tmp // i
        if cnt > 0:
            f[i] = cnt
        i += 1
    if tmp != 1 or f == {}:
        f[tmp] = 1
    return f


n = int(input())
f = factrize(n)
ans = 1
for p in f:
    ans *= p**(f[p] - 1) * (p - 1)
print(ans)

Solution (Python):

n=int(input())
temp=n
from math import floor,sqrt 
ans=n
for i in range(2,floor(sqrt(n))+1):
    if n%i:continue
    while n%i==0:
        n//=i
    ans=ans-ans//i
if n!=1:
    ans=ans-ans//n
print(ans)

Solution (Python):
def prime_factorization(n):  
    res = []
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            cnt = 0
            while n % i == 0:
                cnt += 1
                n //= i
            res.append((i, cnt))
    if n > 1:
        res.append((n, 1))
    return res


def euler_phi(X):
    """
    [1,X]の自然数のうちXと互いに素なものの個数
    """
    if X <= 0:
        raise "INVALID INPUT...X must be natural number"
    pf = prime_factorization(X)
    res = X
    for p, _ in pf:
        res //= p
        res *= (p - 1)
    return res


if __name__ == "__main__":
    N = int(input())
    print(euler_phi(N))

Solution (Python):
"""
オイラー間数値の問題
1,2,…,N1,2,…,N  のうち、NN と互いに素であるものの個数を求めよ。

答え
素因数分解したときに現れる素数をp1，p2，p3...とした時
N(1 ー 1/p1)(1 - 1/p2)(1 - 1/p3)
2の倍数を除去，3の倍数を除去，といった感じ
O(√N)
"""
import copy


p = N = int(input())
prime_numbers = []
d = 2
ans = 1 * N

while d*d <= p:
    if N % d == 0:
        ans *= 1 - 1/d
        while N % d == 0: N //= d
    d += 1

if N > 1:
    ans *= 1 - 1/N

print(int(ans))

Solution (Python):






def euler_phi(n): 
	
	
	result = n; 

	
	
	
	p = 2; 
	while(p * p <= n): 
		
		
		
		if (n % p == 0): 
			
			
			
			while (n % p == 0): 
				n = int(n / p); 
			result -= int(result / p); 
		p += 1; 

	
	
	
	
	if (n > 1): 
		result -= int(result / n); 
	return result; 


n=int(input())

print(euler_phi(n))

Solution (Python):
N=int(input())

def calc_factors(N):
    n = int(N**.5)
    arr = []
    tmp = N
    for i in range(2,n+1):
        if tmp % i == 0:
            while tmp % i == 0:
                arr.append(i)
                tmp = int(tmp/i)
    if tmp != 1: arr.append(tmp) 
    return list(set(arr))
if calc_factors(N) == [N]:
    print(N-1)
else:
    res = N
    for i in calc_factors(N):
        res = res*(1 - i**(-1))
    print(int(res))

Solution (Python):
import sys,bisect,math
from functools import reduce
sys.setrecursionlimit(15000)

N = int(sys.stdin.readline())

def phi(N):
  n = N
  s = set()
  for i in range(2,math.floor(pow(N,0.5))+1):
    while n%i==0:
      s.add(i)
      n = n//i
  if n != 1:
    s.add(n)
  a1 = reduce(lambda a,b: a*b,[e-1 for e in s])
  a2 = reduce(lambda a,b: a*b,[e for e in s])
  
  return a1*N//a2

print(phi(N))

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

def prime_factor(n):
	factor = []
	for i in range(2, int(n ** 0.5) + 1):
		while (n % i == 0):
			factor.append(i)
			n //= i
	if n != 1:
		factor.append(n)
	return factor

def Euler_phi(n):
	divisors = prime_factor(n)
	divisors = set(divisors)
	res = n
	for factor in divisors:
		res = res * (factor - 1) // factor
	return res

print(Euler_phi(n))

Solution (Python):

def prime_factorize(n):
    a = set()
    while n % 2 == 0:
        a.add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.add(n)
    return a

n = int(input())
li = list(prime_factorize(n))
m = len(li)




cnt = 0
for i in range(1, 2 ** m):
  popcount = bin(i).count("1")
  mul = 1
  for j in range(m):
    if (i >> j) & 1:
      mul *= li[j]
  
  if popcount % 2 == 0:
    cnt -= n // mul
  else:
    cnt += n // mul 
print(n - cnt)

Solution (Python):
import math

def prime_factorize(N): 
    exponent = 0
    while N%2 == 0:
        exponent += 1
        N //= 2
    if exponent: factorization = [[2,exponent]]
    else: factorization = []
    i=1
    while i*i <=N:
        i += 2
        if N%i: continue
        exponent = 0
        while N%i == 0:
            exponent += 1
            N //= i
        factorization.append([i,exponent])
    if N!= 1: factorization.append([N,1])
    assert N != 0, "zero"
    return factorization

N = int(input())

f = prime_factorize(N)
ans = N
for p,_ in f:
    ans *= (p-1)/p

print(int(ans))

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

def prime_division(n):
    res = []
    for i in range(2, int(n ** 0.5) + 1):
        cnt = 0
        while n % i == 0:
            cnt += 1
            n //= i
        if cnt != 0:
            res.append([i, cnt])
    if n != 1:
        res.append([n, 1])
    return res

for i in prime_division(n):
    n *= 1 - (1 / i[0])

print(int(n))

Solution (Python):
n=int(input())
p=[]
t=n
for m in range(2,int(n**0.5)+1):
    while t%m==0:
        p.append(m)
        t//=m
if t > 1: p.append(t)
from itertools import groupby
g=groupby(p)
ans=n
for p,c in g:
    ans //= p
    ans *= p-1
print(ans)

Solution (Python):
import collections

n = int(input())

def prime_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


c = collections.Counter(prime_factorize(n))


for i in c.keys():
    n *= (i - 1)
for j in c.keys():
    n //= j
print(n)

Solution (Python):
def euler_phi(n):
    phi = n
    for i in set(prime_factorize(n)):
        phi *= (1 - (1 / i))
    return phi

def prime_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

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