def prime_list(n):
plist = []
while n != 1:
w = 0
for i in range(1, n + 1):
for j in range(1, i):
if i % j == 0:
w = 1
if w == 1:
if n % i == 0:
plist.append(i)
n = n // i
return plist
def proper_fractions(n):
lrsult = [i for i in range(1, n)]
lprime = prime_list(n)
for i in range(1, n):
for j in lprime:
if i % j == 0 and i in lrsult:
lrsult.remove(i)
break
ll = list((set(lrsult)))
return len(ll)
def proper_fractions(n: int) -> int:
list1 = []
for i in range(1,n):
if (i % 2 == 0 and n%2 == 0) or (i % 3 == 0 and n%3==0) or (i % 5 == 0 and n%5==0):
pass
else:
list1.append(i)
print(list1)
return len(list1)
def proper_fractions(n: int) -> int:
prime_factor = set()
tmp_n = n
for i in range(2,int(math.sqrt(n))+1):
while n%i==0:
prime_factor.add(i)
n //= i
if n>1:
prime_factor.add(n)
prime_factor=sorted(list(prime_factor))
res_li = []
def inner_func(l1,ln,tmp):
if len(tmp) == ln:
return res_li.append(tmp)
for i in range(len(l1)):
inner_func(l1[i+1:],ln,tmp+[l1[i]])
res_final=tmp_n - 1 - sum( tmp_n // prime_factor[i] - 1 for i in range(len(prime_factor)))
for j in range(2,len(prime_factor)+1):
inner_func(prime_factor, j, [])
if j%2==0:
res_final += sum(tmp_n // reduce(lambda x,y:x*y,i) -1 for i in res_li)
res_li = []
else:
res_final -= sum(tmp_n // reduce(lambda x, y: x * y, i) - 1 for i in res_li)
res_li = []
return res_final
def GCD(a,b):
if a < b:
a, b = b, a
# 判断是否能整除，若能整除，直接返回被除数
if a % b == 0:
return b
# 若不能整除，则返回函数GCD，参数做相应变化
else:
return GCD(b, a % b)
def proper_fractions(n: int) -> int:
s=[1 for i in range(1,n) if GCD(i,n)==1] if n>1 else [0]
return sum(s)
如果 n 是分子，d 是分数的分母，当且仅当 GCD（n，d）==1，则该分数被定义为最简分数。