对正整数 n，函数 () n 定义为：小于等于 n 正整数中与 n 互质的正整数的数目。如： (12) 4  ，因 为 1,5,7,11 均和 12 互质。则： (500)  =

对正整数 n，函数 φ ( n ) varphi left( nright) φ(n)定义为：小于等于 n 正整数中与 n 互质的正整数的数目。如： φ ( 12 ) varphi left( 12right) φ(12)=4 ，因
为 1,5,7,11 均和 12 互质。则 φ ( 500 ) varphi left( 500right) φ(500)=

1、

#互质 最大公因数为1 def fun(n): c=0 for i in range(1,n+1): for j in range(2,n+1): if i%j==0 and n%j==0: break if j==n: c+=1 return c print(fun(500)) 12345678910111213

2、

#辗转相除法算最大公因数 欧几里得算法 def gac(p,q): if q==0: return p else: return gac(q,p%q) # print(gac(255,55)) def fun(n): c=0 for i in range(1,n+1): if gac(i,500)==1: c+=1 return c print(fun(500)) 1234567891011121314

单论此题 第一种更高效。