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: Wrong Answer

Solution code:
from collections import defaultdict

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

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

Submission status: Wrong Answer

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:
        f = True
        break
    if x==len(primes)-1:
        f = False
        break
    if tmpn%primes[x]==0:
        anslist.append(primes[x])
        tmpn = tmpn/primes[x]
        x -= 1
    x+=1
# print anslist
if f:
    ansset = set(anslist)
    # print ansset
    ans = n
    for tmp in ansset:
        ans *= (1-1.0/tmp)
    print int(ans)
else:
    print n-1

Submission status: Wrong Answer

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()
pdset = set(prime_decomposition(n))
if len(pdset)==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: Wrong Answer

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

import sys
import io

count = 1
n=int(input()) 
for x in range(2,n-1):
	if n%x != 0 :count = count+1

print count

Submission status: Wrong Answer

Solution code:
input = int(input())
buf = input
result = 1
for i in range(2,input):
    if buf%i==0:
        result *= (1 - 1/i)
    while buf%i==0:
        buf /= i
result *= input
print(int(result))

Submission status: Wrong Answer

Solution code:
input = int(input())
buf = input
result = 1
i = 2;
while i*i <= buf:
    if buf%i==0:
        result *= (1 - 1/i)
    while buf%i==0:
        buf /= i
    i += 1
if buf>1:
    result *= (1-1/buf)    
result *= input
print(int(result))

Submission status: Wrong Answer

Solution code:
import sys
x = int(input())
count = 0
for a in range(2,x):
    if x % a == 0:
        count+=1

print(count)

Submission status: Wrong Answer

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
   
    res = res - res//a

    return res


x = int(input())


print(euler(x))

Submission status: Wrong Answer

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 rst == n:
        rst = 2
    elif x > s:
        rst *= 1 - 1/x
    return int(rst)

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

Submission status: Wrong Answer

Solution code:
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

n = int(raw_input())

count = 0
for i in range(1,n):
    b = i
    g = gcd(n,b)
    l = n*b/g
    if l == 1:
        count += 1

Submission status: Wrong Answer

Solution code:
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

n = int(raw_input())

count = 0
for i in range(1,n):
    b = i
    g = gcd(n,b)
    print g
    if g == 1:
        count += 1
print count

Submission status: Wrong Answer

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)

for i in div:
	for j in range(1,n/i):
		p[i*j] = 0

print sum(p)

Submission status: Wrong Answer

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] = 0
for i in div:
	p[i::i] = [0 for x in range(i,n+1,i)]
	
print sum(p)

Submission status: Wrong Answer

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] = 0
for i in div:
	p[i::i] = [0 for x in range(i,n+1,i)]
	
print sum(p) if n>3 else sum(p)-1

Submission status: Wrong Answer

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

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

phai = n
for i in div:
	phai *= (1-1/float(i))
print int(phai)

Submission status: Wrong Answer

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+3,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: Wrong Answer

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

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+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_input())
plist = make_plist(n)
pfacts = get_pfact(plist,n)
print get_phai(n,pfacts)

Submission status: Wrong Answer

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))+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_input())
plist = make_plist(n)
pfacts = get_pfact(plist,n)
print get_phai(n,pfacts)

Submission status: Wrong Answer

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_input())
plist = make_plist(n)
pfacts = get_pfact(plist,n)
print get_phai(n,pfacts)

Submission status: Wrong Answer

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_input())
plist = make_plist(n)
pfacts = get_pfact(plist,n)
print get_phai(n,pfacts)

Submission status: Wrong Answer

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+2):
		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_input())
plist = make_plist(n)
pfacts = get_pfact(plist,n)
print get_phai(n,pfacts)

Submission status: Wrong Answer

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(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: Wrong Answer

Solution code:
n = int(raw_input())
now = n
i = 2
while i <= n and now != 1:
	if now%i == 0:
		n *= (i-1)/i
		while now%i==0:
			now /= i
	i += 1
print n

Submission status: Time Limit Exceeded

Solution code:
import math
import random
class Prime:
    seed_primes=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
    def is_prime(self,n):
        is_prime_common=self.is_prime_common(n)
        if is_prime_common is not None:return is_prime_common
        if n<2000000:return self.is_prime_brute_force(n)
        return self.is_prime_miller_rabin(n)
    def is_prime_common(self,n):
        if n==1:return False
        if n in Prime.seed_primes:return True
        if any(map(lambda x:n%x==0,self.seed_primes)):return False
    def is_prime_brute_force(self,n):
        for k in range(2,int(math.sqrt(n))+1):
            if n%k==0:return False
        return True
    def is_prime_miller_rabin(self,n):
        d=n-1
        while d&1==0:d>>=1
        witnesses=self.get_witnesses(n)
        for w in witnesses:
            y=pow(w,d,n)
            while d!=n-1and y!=1and y!=n-1:
                y=y*y%n
                d<<=1
            if y!=n-1and d&1==0:return False
        return True
    def get_witnesses(self,num):
        def _get_range(num):
            if num<2047:return 1
            if num<1373653:return 2
            if num<25326001:return 3
            if num<3215031751:return 4
            if num<2152302898747:return 5
            if num<3474749660383:return 6
            if num<341550071728321:return 7
            if num<3825123056546413051:return 9
            return 12
        return self.seed_primes[:_get_range(num)]
    def gcd(self,a,b):
        if a<b:return self.gcd(b,a)
        if b==0:return a
        while b:a,b=b,a%b
        return a
    @staticmethod
    def f(x,n,seed):
        p=Prime.seed_primes[seed%len(Prime.seed_primes)]
        return(p*x+seed)%n
    def find_factor(self,n,seed=1):
        if self.is_prime(n):return n
        x,y,d=2,2,1
        count=0
        while d==1:
            count+=1
            x=self.f(x,n,seed)
            y=self.f(self.f(y,n,seed),n,seed)
            d=self.gcd(abs(x-y),n)
        if d==n:
            return self.find_factor(n,seed+1)
        return self.find_factor(d)
    # nのすべての素因数を見つける
    def find_factors(self,n):
        primes={}
        if self.is_prime(n):
            primes[n]=1
            return primes
        while n>1:
            factor=self.find_factor(n)
            primes.setdefault(factor,0)
            primes[factor]+=1
            n//=factor
        return primes
n=int(input())
a=n
for i in Prime().find_factors(n):
    a=a//i*~-i
print(a)

Submission status: Time Limit Exceeded

Solution code:
a=int(input())
li=[0]*10000000
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: Time Limit Exceeded

Solution code:
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)

n = int(input())

cnt = 2
for i in range(2, n-1):
    if gcd(i, n) == 1:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

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

import sys
import io

count = 1
n=int(input())
 
for x in range(2,n):
	m=n
	gcd=x
	while m%gcd !=0 :
		r=m%gcd
		m   = gcd
		gcd = r
	if gcd == 1: count = count+1

print count

Submission status: Time Limit Exceeded

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

import sys
import io

count = 1
n=int(input())
if n%2 != 0:
	for x in range(2,n):
	
		m=n
		gcd=x
		while m%gcd !=0 :
			r=m%gcd
			m   = gcd
			gcd = r
		if gcd == 1: count = count+1
else:
	
	for x in range(3,n,2):
	
		m=n
		gcd=x
		while m%gcd !=0 :
			r=m%gcd
			m   = gcd
			gcd = r
		if gcd == 1: count = count+1
print count

Submission status: Time Limit Exceeded

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

import sys
import io

count = 1
n=int(input())
if n%2 != 0:
	for x in range(2,n):
	        if n%x == 0:continue

		m=n
		gcd=x
		while m%gcd !=0 :
			r=m%gcd
			m   = gcd
			gcd = r
		if gcd == 1: count = count+1
else:
	
	for x in range(3,n,2):
	        if n%x == 0:continue

		m=n
		gcd=x
		while m%gcd !=0 :
			r=m%gcd
			m   = gcd
			gcd = r
		if gcd == 1: count = count+1
print count

Submission status: Time Limit Exceeded

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

"""
input:
1000000

output:
400000
"""

import sys


def gcd(x, y):
    if x < y:
        x, y = y, x

    while y > 0:
        r = x % y
        x = y
        y = r

    return x


def phi(n):
    ans = 0

    for k in range(1, n + 1):
        if gcd(n, k) == 1:
            ans += 1

    return ans


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

Submission status: Time Limit Exceeded

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

"""
input:
1000000

output:
400000
"""

import sys


def is_prime(n):
    if n == 2:
        return True
    elif n < 2 or not n % 2:
        return False

    return pow(2, n - 1, n) == 1


def phi(n):
    y = n
    for k in range(2, n + 1):
        if not n % k and is_prime(k):
            y -= y / k
    return int(y)


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

Submission status: Time Limit Exceeded

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

"""
input:
1000000

output:
400000
"""

import sys
import math


def is_prime(n):
    if n == 2:
        return True
    elif n < 2 or not n % 2:
        return False

    k = 3
    while k <= math.sqrt(n):
        if not n % k:
            return False
        k += 2

    return True


def phi(n):
    y = n
    for k in range(2, n + 1):
        if not n % k and is_prime(k):
            y -= y / k
    return int(y)


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

Submission status: Time Limit Exceeded

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

"""
input:
1000000

output:
400000
"""

import sys


def is_prime(n):
    if n == 2:
        return True
    elif n < 2 or not n % 2:
        return False

    return pow(2, n - 1, n) == 1


def min_prime_factor(n):
    if is_prime(n):
        return n
    else:
        k = 2
        while True:
            if not n % k:
                break
            k += 1
    return k


def phi(n):
    ans = n
    while True:
        p = min_prime_factor(n)
        if n == 1:
            break
        while n % p == 0:
            # print(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: Time Limit Exceeded

Solution code:
n=int(input())
m=n;i=2
while i<=n and m!=1:
    if not m%i:
        n=n*(i-1)//i
        while not m%i:m//=i
    i+=1
print(n)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def gcd(x,y):
    r = x%y
    if r==0:
        return y
    else:
        return gcd(y,r)
input = int(input())
cnt = 1
for i in range(2,input):
    if gcd(input,i) == 1:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
input = int(input())
buf = input
result = 1
for i in range(2,input+1):
    if buf%i==0:
        result *= (1 - 1/i)
    while buf%i==0:
        buf /= i
result *= input
print(int(result))

Submission status: Time Limit Exceeded

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 // 2:
        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: Time Limit Exceeded

Solution code:
import sys
def gcd(a,b):
    if(b == 0):
        return a
    else:
        c = b
        b = a%b
        a = c
        return(gcd(a,b))

x = int(input())
count = 0
for y in range(1,x+1):
    if gcd(x,y) == 1:
        count+=1

print(count)

Submission status: Time Limit Exceeded

Solution code:
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

n = int(raw_input())

count = 0
for i in range(1,n):
    b = i
    g = gcd(n,b)
    if g == 1:
        count += 1
print count

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
now = n
i = 2
while i <= n and now != 1:
	if now%i == 0:
		n = n*(i-1)/i
		while now%i==0:
			now /= i
	i += 1
print n

Submission status: Memory Limit Exceeded

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def primeFact(n):
    """
    nの素因数をlistで返す
    """
    factors = []
    i = 2
    while i*i <= n:
        if n % i == 0:
            n //= i
            factors.append(i)
        else:
            i += 1
    if n > 1:
        factors.append(n)
    return factors


N = int(input())
fa = primeFact(N)
ans = range(1, N)
for f in fa:
    ans = list(filter(lambda x: x % f != 0, ans))
print(len(ans))

Submission status: Memory Limit Exceeded

Solution code:
n = int(input())
a = [1 for i in range(n + 1)]
a[0] = 0
a[1] = 1
a[n] = 0
for i in range(2, int(n**0.5 + 1)):
    if n % i == 0:
        for j in range(i, n, i):
            a[j] = 0
        for j in range(n // i, n, n // i):
            a[j] = 0
print(sum(a))

Submission status: Memory Limit Exceeded

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:
        f = True
        break
    if x>len(primes)-1:
        f = False
        break
    if tmpn%primes[x]==0:
        anslist.append(primes[x])
        tmpn = tmpn/primes[x]
        x -= 1
    x+=1
# print anslist
if f:
    ansset = set(anslist)
    # print ansset
    ans = n
    for tmp in ansset:
        ans *= (1-1.0/tmp)
    print int(ans)
else:
    print n-1

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
# print(prime_list)
for p in set(prime_list):
    answer *= (1 - Fraction(1, p))
print(answer)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
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 = []
#find prime numbers in 1-sqrt(n)
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)