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

Submission status: Accepted

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

    ans*=(1-1/temp)
    #print (ans)

print(int(ans))


                
       

def gcd(a,b): #?????§??¬?´???°???????????°??????
    r=0
    while True:
       r=a%b
       if r==0:
           break
       a=b
       b=r
    return b

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
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)
        # print(tmp)
        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))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# Aizu Problem NTL_1_D: Euler's Phi Function
#
import itertools
import sys, math, os

# read input:
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))

Submission status: Accepted

Solution code:
def is_prime(x):
    # Perform prime number discrimination for odd numbers of 3 or more.
    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()

Submission status: Accepted

Solution code:
import sys
def euler(a):
    i = 2
    res = a
    #standard = 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))

Submission status: Accepted

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

Submission status: Accepted

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: Accepted

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

Submission status: Accepted

Solution code:

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from itertools import product

input = sys.stdin.readline


def calc_prime_factors(n, count=False):
    """Trial division"""
    factors = []
    # factor: 2
    while n % 2 == 0:
        factors.append(2)
        n //= 2
    # factor: 3, 5, 7, 11, ...
    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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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): # divを因数にもちうるものであるため、i=0は不適
    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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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):
    # mを与えると、高々その素因数まで見て、残りは分解せずにそのまま出力する
    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)

Submission status: Accepted

Solution code:
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):
        # オイラーのφ関数
        # 1からnのうち，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()

Submission status: Accepted

Solution code:
# 1..n でnと違いに素なものの個数
# エラトステネスの逆っぽい
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):
    # root n まで見て残っているならそれはOK
    # 個数のみ保持するので何個消したかを残しておけば良い
    # n <= 10**9
    total = n  # 1...n のtotal
    lis = list(set(prime_divide(n)))
    l = len(lis)
    # bit全探索で1...2**n-1 まで探すと良い
    for i in range(1, 2 ** l):
        cum = 1  # 累積
        cnt = 0
        for j in range(l):
            if i >> j & 1:
                # bitが立っている。
                cum *= lis[j]
                cnt += 1
        if cnt % 2:  # 奇数個なら-
            total -= n // cum
        else:
            total += n // cum
    return total


print(euler_fai(n))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def factrize(x):
    # 試し割りによる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)

Submission status: Accepted

Solution code:

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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
"""
オイラー間数値の問題
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))

Submission status: Accepted

Solution code:
# https://tjkendev.github.io/procon-library/python/prime/eulers-totient-function.html
# https://qiita.com/drken/items/a14e9af0ca2d857dad23#%E5%95%8F%E9%A1%8C-6-%E3%82%AA%E3%82%A4%E3%83%A9%E3%83%BC%E9%96%A2%E6%95%B0
# オイラー関数
# 1,2,...,NのうちNと互いに素であるものの個数
# Python3 program to calculate 
# Euler's Totient Function 
def euler_phi(n): 
	
	# Initialize result as n 
	result = n; 

	# Consider all prime factors 
	# of n and subtract their 
	# multiples from result 
	p = 2; 
	while(p * p <= n): 
		
		# Check if p is a 
		# prime factor. 
		if (n % p == 0): 
			
			# If yes, then 
			# update n and result 
			while (n % p == 0): 
				n = int(n / p); 
			result -= int(result / p); 
		p += 1; 

	# If n has a prime factor 
	# greater than sqrt(n) 
	# (There can be at-most 
	# one such prime factor) 
	if (n > 1): 
		result -= int(result / n); 
	return result; 


n=int(input())

print(euler_phi(n))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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])
  #print(N,a1,a2)
  return a1*N//a2

print(phi(N))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# 素因数分解
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)

# print(li)
# print(m)

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]
  # print(popcount, bin(i), j, mul)
  if popcount % 2 == 0:
    cnt -= n // mul
  else:
    cnt += n // mul 
print(n - cnt)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

def prime_factorize(n):
    # Return list of prime factorized result
    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)))

Submission status: Accepted

Solution code:
"""
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  # the keys are unsorted


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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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: # 最後がiで割り切れた場合は1が残り、そうでない場合は残りも因数となる。これは必ず因数の中で最大になる。(そうでないなら最後に割ったiより先に因数になってる)
        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)

Submission status: Accepted

Solution code:
import math

n = int(input())

#Euler関数の性質
#1:pが素数のときEuler(p**k)=p**k-p**(k-1)
#2:gcd(m,n)=1のときEuler(mn)=Euler(m)*Euler(n)
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 #このときaが常に素数
                while n % a == 0:
                    n //= a
                    b += 1
                break
        if a == 1: #このときはnが素数
            return n-1
        else:
            return (a**b-a**(b-1))*Euler(n)

print(Euler(n))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

    # 今回のアルゴリズムについて
    # nが素数でない⇔nは√n以下の素因数を持つ⇒√n以下のすべての素数を列挙して、それでnを割っていってみる。
    #√n以下の素数をすべて書き出すために、エラトステネスの篩を使用する。t以下の素数をすべて列挙するためには√tまでの素数について調べれば十分なので、√nまでの素数を書き出すためには√√nまでの数について真面目に篩をかければいい。

    nOrigin = n
    n = n**0.5
    # n(=√input())以下の素数のリストをエラトステネスにより作成する
    # 素数の位置にはその数が、合成数の位置には-1が格納されているリストを作成
    # 0が格納されているのはまだ確認していない数。
    numlist = [0 for i in range(int(n) + 1)]
    numlist[0] = -1
    numlist[1] = -1

    #√√n以下の数について篩をかけていく
    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

    #√√nより大きい数で、篩にかからなかった数は素数。
    while t <= n:
        if numlist[t] == 0:
            numlist[t] = t
        t += 1

    #√n以下の数で割っていく。
    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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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