Buggy python submission (verdict: Time Limit Exceeded):
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

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

Buggy python submission (verdict: Runtime Error):
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

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

Buggy python submission (verdict: Runtime Error):
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

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

Buggy python submission (verdict: Runtime Error):
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)

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

Buggy python submission (verdict: Runtime Error):
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)

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

Buggy python submission (verdict: Runtime Error):
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)

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

Buggy python submission (verdict: Runtime Error):
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)

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

Buggy python submission (verdict: Runtime Error):
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)

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

Buggy python submission (verdict: Runtime Error):
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)

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

Buggy python submission (verdict: Time Limit Exceeded):
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

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