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



Sample input:
6


Sample output:
2

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
#D
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])
#print(fact)
    
ans = n
for f in fact:
    p,c = f
    ans*=(1-1/p)
    
print(int(ans))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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()
    # 終点はルート切り捨て+1
    for i in range(2, int(sqrt(num))+1):
        # 素因数分解：小さい方から割れるだけ割って素数をカウント
        while num % i == 0:
            num //= i
            d[i] += 1
        # 1まで分解したら終了
        if num == 1:
            break
    # 最後に残ったnumは素数(ただし1^1は1^0なので数に入れない)
    if num != 1:
        d[num] += 1
    return d

N = INT()

primes = factorize(N)
ans = N
# Nが持つ各素数について、オイラーのファイ関数を使っていく
for k in primes.keys():
    ans *= 1 - 1/k
print(int(ans))

Submission status: Accepted

Solution code:
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)
  #k.append(1)

  return k

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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])))

Submission status: Accepted

Solution code:
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 = []  # type: ignore
    compute_prime_factor(n)
    print(euler_phi(n, prime_factors))

Submission status: Accepted

Solution code:
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
        #print(n)
        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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	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): #listをスペースごとに分ける
	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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
#オイラーのφ関数
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
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))
#print(l1)
#print(l2)

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(x)
#    print(l3)
#    print(l4)
#    print(l5)

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env 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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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())))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Runtime Error

Solution code:
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, 1))
    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')

Submission status: Runtime Error

Solution code:
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())))

Submission status: Runtime Error

Solution code:
a=int(input())
li=[0]*1000001
count=1
i=2 # ??????????????°
while i<a:    
    r=0
    ta=a
    b=i
    if li[i]!=1:
        while True:
                    
            r=ta%b
            if r==0:
                break
            ta=b
            b=r
        if b==1:
            count+=1
        else:
            temp=i
            l=2
            while True:
               li[temp*l]=1
               l+=1
               if temp*l>a:
                   break
    i+=1                
print(count)

Submission status: Runtime Error

Solution code:
def mark(s, x):
    for i in xrange(x + x, len(s), x):
        s[i] = False

def sieve(n):
    s = [True] * n
    for x in xrange(2, int(n**0.5) + 1):
        if s[x]: mark(s, x)
    return [i for i in xrange(0,n) if s[i] and i > 1]

n = input()
tmpn =n
primes = sieve(n/2+1)
# print primes
anslist = []
x = 0
while True:
    if tmpn == 1:
        break
    if tmpn%primes[x]==0:
        anslist.append(primes[x])
        tmpn = tmpn/primes[x]
        x -= 1
    x+=1
# print anslist
ansset = set(anslist)
# print ansset
ans = n
for tmp in ansset:
    ans *= (1-1.0/tmp)
print int(ans)

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
import math
 
n = m = int(raw_input())
r = int(math.sqrt(n))
sqrt = int(math.sqrt(r))
p = [1]*r
p[0] = 0
for i in range(1,sqrt):
    if p[i]:
        p[2*i+1::i+1] = [0 for x in range(2*i+1,r,i+1)]
  
prime=[]
for i in range(r):
    if p[i]:
        prime.append(i+1)

a = []
for i in range(len(prime)):
    if n % prime[i] == 0:
        a.append(prime[i])
        n /= prime[i]
        
if n != 1:
    a.append(n)

count = 0
for i in range(m):
    flag = 1
    for j in a:
        if i%j == 0:
            flag = 0
            break
    if flag == 1:
        count += 1

print count

Submission status: Runtime Error

Solution code:
import math
n = int(raw_input())
sqrt = int(math.sqrt(n))
p = [1]*(n+1)
p[0] = 0
for i in range(2,sqrt+1):
	if p[i]:
		p[2*i::i] = [0 for x in range(2*i,n+1,i)]

div = []
for i in range(2,n/2+1):
	if p[i] and n%i == 0:
		div.append(i)

p = [1]*(n+1)
p[0],p[n] = 0,0
for i in div:
	p[i::i] = [0 for x in range(i,n+1,i)]
	
print sum(p)

Submission status: Runtime Error

Solution code:
import math

def plist(n):
	sqrt = int(math.sqrt(n))
	p = [1]*(sqrt+3)
	p[0] = 0
	for i in range(2,int(math.sqrt(sqrt))+2):
		if p[i]:
			p[2*i::i] = [0 for x in range(2*i,sqrt+1,i)]
	return p

def get_pfact(p,n):
	div = []
	sqrt = int(math.sqrt(n))
	for i in range(2,sqrt+3):
		if p[i] and n%i == 0:
			div.append(i)
	return div

def phai(n,div):
	ans = n
	for pf in div:
		ans *= (1-1/float(pf))
	return int(ans)

# main	
n = int(raw_input())
p = plist(n)
div = get_pfact(p,n)
print phai(n,div)

Submission status: Runtime Error

Solution code:
import math

def make_plist(n):
	sqrt = int(math.sqrt(n))
	plist = [1]*(sqrt+3)
	plist[0] = 0
	for i in range(2,int(math.sqrt(sqrt))+2):
		if plist[i]:
			plist[2*i::i] = [0 for x in range(2*i,sqrt+3,i)]
	return plist

def get_pfact(plist,n):
	pfact = []
	sqrt = int(math.sqrt(n))
	for i in range(2,sqrt+1):
		if plist[i] and n%i == 0:
			pfact.append(i)
	if p[n] == 1: pfact.append(n)
	return pfact

def get_phai(n,pfacts):
	phai = n
	for pfact in pfacts:
		phai *= (1-1/float(pfact))
	return int(phai)

# main	
n = int(raw_input())
plist = make_plist(n)
pfacts = get_pfact(plist,n)
print get_phai(n,pfacts)

Submission status: Runtime Error

Solution code:
import math

def make_plist(n):
    sqrt = int(math.sqrt(n))
    plist = [1]*(sqrt+3)
    for i in range(2,int(math.sqrt(sqrt))+3):
        if plist[i]:
            plist[2*i::i] = [0 for x in range(2*i,sqrt+3,i)]
    return plist

def get_pfact(plist,n):
    pfact = []
    sqrt = int(math.sqrt(n))
    for i in range(2,sqrt+3):
        if plist[i] and n%i == 0:
            pfact.append(i)
    else:
        if len(pfact) == 0: pfact.append(n)
    return pfact

def get_phai(n,pfacts):
    phai = n
    for pfact in pfacts:
        phai *= (1-1/float(pfact))
    return int(phai)

# main
n = int(raw_intput())
plist = make_plist(n)
pfacts = get_pfact(plist,n)
print get_phai(n,pfacts)

Submission status: Runtime Error

Solution code:
import math

def make_plist(n):
	sqrt = int(math.sqrt(n))
	plist = [1]*(n/2+1)
	for i in range(2,int(math.sqrt(sqrt))+3):
		if plist[i]:
			plist[2*i::i] = [0 for x in range(2*i,sqrt+3,i)]
	return plist

def get_pfact(plist,n):
	pfact = []
	sqrt = int(math.sqrt(n))
	for i in range(2,sqrt+3):
		if plist[i] and n%i == 0:
			pfact.append(i)
			if plist[n/i]:
				pfact.append(i)
	else:
		if len(pfact) == 0: pfact.append(n)
	return pfact

def get_phai(n,pfacts):
	phai = n
	for pfact in pfacts:
		phai *= (1-1/float(pfact))
	return int(phai)

# main	
n = int(raw_input())
plist = make_plist(n)
pfacts = get_pfact(plist,n)
print get_phai(n,pfacts)

Submission status: Runtime Error

Solution code:
import math

def make_plist(n):
	sqrt = int(math.sqrt(n))
	plist = [1]*(n/2+1)
	for i in range(2,int(math.sqrt(sqrt))+3):
		if plist[i]:
			plist[2*i::i] = [0 for x in range(2*i,n/2+1,i)]
	return plist

def get_pfact(plist,n):
	pfact = []
	sqrt = int(math.sqrt(n))
	for i in range(2,sqrt+3):
		if plist[i] and n%i == 0:
			pfact.append(i)
			if plist[n/i]:
				pfact.append(n/i)
	else:
		if len(pfact) == 0: pfact.append(n)
	return pfact

def get_phai(n,pfacts):
	phai = n
	for pfact in pfacts:
		phai *= (1-1/float(pfact))
	return int(phai)

# main	
n = int(raw_input())
plist = make_plist(n)
pfacts = get_pfact(plist,n)
print get_phai(n,pfacts)